Hard Problem

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, \ldots, a_{i + m - 1}) - \max(a_{i + m}, \ldots, a_{i + 2m - 1})\right| \le k$.

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 of $(a_{i+m-1} + 10) \cdot f_m$ over all good subsegments. Since this number can be large, print it modulo 998244353.

The first line contains a single integer $t$ ($1 \le t \le 10^4$), the number of test cases. Each test case starts with a line containing two integers $n$ and $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le \min(n, 10)$).

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

The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

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