{"problem":{"name":"I hate ABC","description":{"content":"Find the number, modulo $998244353$, of strings $S$ of length $N$ consisting of `A`, `B`, `C` such that the following value equals $K$: *   The maximum length of a (not necessarily contiguous) subseq","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc209_e"},"statements":[{"statement_type":"Markdown","content":"Find the number, modulo $998244353$, of strings $S$ of length $N$ consisting of `A`, `B`, `C` such that the following value equals $K$:\n\n*   The maximum length of a (not necessarily contiguous) subsequence of $S$ that does not contain `ABC` as a (not necessarily contiguous) subsequence\n\nYou are given $T$ test cases. Solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 2 \\times 10^5$\n*   $1 \\le N \\le 10^6$\n*   $\\max(0,N-100) \\le K \\le N$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N\\ K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc209_e","tags":[],"sample_group":[["4\n4 3\n8 6\n123 100\n123456 123400","9\n462\n741573397\n255048895\n\nFor the first test case, for example, `ACBC` satisfies the condition. `ACBC` itself contains `ABC` as a subsequence, and `ACC` does not contain `ABC` as a subsequence, so the maximum length of a subsequence that does not contain `ABC` as a subsequence is $3$. Other examples that satisfy the condition include `AABC` and `ABCA`."]],"created_at":"2026-03-03 11:01:14"}}