시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB0000.000%

문제

You are given an integer array $a_1, \ldots, a_n$. A subsegment of even length $a_i,\ldots, a_{i + 2m - 1}$ is called good if $\left|\max(a_i,\dots, a_{i + m - 1}) - \max(a_{i + m}, \ldots, a_{i + 2m - 1})\right| \leq k$.

Let us define an integer sequence $f$ as follows:

  • $f_1 = 3240$
  • $f_2 = 3081$
  • $f_3 = 2841$
  • $f_4 = 343$
  • $f_i = f_{i-1} \cdot 223 + f_{i-2} \cdot 229 + f_{i-3} \cdot f_{i-4} \cdot 239 + 17$ for $i > 4$

Calculate the sum $(a_{i+m-1} + 10) \cdot f_{m}$ among all good subsegments. Since this number can be large, print it modulo $998\,244\,353$.

입력

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) --- the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1 \leq n \leq 5 \cdot 10^5$, $0 \leq k \leq \min (n, 10)$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

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

출력

For each test case, print a single integer --- the answer to the problem.

예제 입력 1

3
6 0
3 1 3 1 3 1
8 4
5 8 4 6 5 7 8 5
7 3
2 1 3 2 2 1 3

예제 출력 1

144768
745933
448953