I hate ABC

AtCoder

IDarc209_e

Time4000ms

Memory256MB

Difficulty—

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) subsequence of $S$ that does not contain `ABC` as a (not necessarily contiguous) subsequence You are given $T$ test cases. Solve each of them. ## Constraints * $1 \le T \le 2 \times 10^5$ * $1 \le N \le 10^6$ * $\max(0,N-100) \le K \le N$ ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ Each case is given in the following format: $N\ K$ [samples]

Samples

Input #1

4
4 3
8 6
123 100
123456 123400

Output #1

9
462
741573397
255048895

For 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`.

API Response (JSON)

{
  "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) subseq...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments