E. Eight-thousand-year Wait
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

To commemorate the eight-thousand-year wait, Iroha and Kaguya will edit an echo sequence inside the virtual space "Tsukuyomi". Whenever two echoes are perfectly in sync, the stage will light up with a flash. They want to know: how many echo sequences can make the stage flash exactly $$$k$$$ times?

More specifically, they are given an array $$$a$$$ of length $$$n$$$.

For a sequence $$$b$$$ of length $$$m$$$, define its number of flashes as $$$$$$ f\left(b\right) = \left|\left\{i | 1 \leq i \leq m - 1, b_i = b_{i+1}\right\}\right| $$$$$$ that is, the number of times two adjacent elements in the sequence are equal.

You need to compute, among the $$$2^n$$$ subsequences$$$^{\text{∗}}$$$ of $$$a$$$, how many subsequences $$$b$$$ have exactly $$$k$$$ flashes (i.e. $$$f\left(b\right) = k$$$). Since the answer may be very large, print it modulo $$$998244353$$$.

$$$^{\text{∗}}$$$A sequence $$$b$$$ is a subsequence of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 2 \times 10^5$$$, $$$0 \leq k \leq 200$$$) — the length of the array $$$a$$$ and the desired number of flashes.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer — the number of subsequences whose number of flashes is $$$k$$$, taken modulo $$$998244353$$$.

Example
Input
2
4 1
1 2 2 1
3 0
1 1 2
Output
5
6
Note

In the first test case, $$$a = [1, 2, 2, 1]$$$, and the $$$16$$$ subsequences are as follows:

  • $$$b = []$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1] = [1]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1, a_2] = [1, 2]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1, a_2, a_3] = [1, 2, 2]$$$, the number of flashes is $$$1$$$.
  • $$$b = [a_1, a_2, a_3, a_4] = [1, 2, 2, 1]$$$, the number of flashes is $$$1$$$.
  • $$$b = [a_1, a_2, a_4] = [1, 2, 1]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1, a_3] = [1, 2]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1, a_3, a_4] = [1, 2, 1]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_1, a_4] = [1, 1]$$$, the number of flashes is $$$1$$$.
  • $$$b = [a_2] = [2]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_2, a_3] = [2, 2]$$$, the number of flashes is $$$1$$$.
  • $$$b = [a_2, a_3, a_4] = [2, 2, 1]$$$, the number of flashes is $$$1$$$.
  • $$$b = [a_2, a_4] = [2, 1]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_3] = [2]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_3, a_4] = [2, 1]$$$, the number of flashes is $$$0$$$.
  • $$$b = [a_4] = [1]$$$, the number of flashes is $$$0$$$.
Therefore, there are $$$5$$$ subsequences whose number of flashes is $$$1$$$.