어려운 문제

정수 배열 $a_1, \ldots, a_n$이 주어진다. 길이가 짝수인 부분 구간 $a_i, \ldots, a_{i + 2m - 1}$에서 앞 절반 $a_i, \ldots, a_{i + m - 1}$의 최댓값과 뒤 절반 $a_{i + m}, \ldots, a_{i + 2m - 1}$의 최댓값의 차이의 절댓값이 $k$ 이하이면, 이 구간을 좋은 구간이라고 한다.

정수 수열 $f$를 다음과 같이 정의한다.

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

모든 좋은 부분 구간에 대해 $(a_{i+m-1} + 10) \cdot f_m$의 합을 구하라. 값이 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$, $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le \min(n, 10)$)가 주어진다.

다음 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)이 주어진다.

모든 테스트 케이스의 $n$의 합은 $5 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 답을 한 줄에 출력한다.