Range Count Subsequence Query

問題文

整数 $K$ 、 $D$ 、および長さ $N$ の非負整数列 $(a_1, a_2, \ldots, a_N)$ が与えられます。

以下のクエリに $Q$ 回答えてください。

• $i$ 番目のクエリでは整数 $l_i,r_i \ (1 \leq l_i \leq r_i \leq N)$ が与えられます。非負整数列 $(a_{l_{i}}, a_{l_{i}+1}, \ldots a_{r_{i}})$ の長さ $K$ の部分列のうち、総和が $D$ の倍数であるものの個数を $998244353$ で割ったあまりを求めてください。

注意

• $2$ つの部分列が数列として同じであっても、元の数列での位置が異なっていた場合、異なる部分列として数えます。
• 数列の長さ $K$ の部分列とは、数列の要素のうち $K$ 個を選んで、それらを順番を変えずに取り出して並べた数列のことを指します。

制約

• $1 \leq N \leq 10^5$
• $1 \leq K, D \leq 10$
• $0 \leq a_i \leq 10^9 \ (1 \leq i \leq N)$
• $1 \leq Q \leq 2000$
• $1 \leq l_i \leq r_i \leq N \ (1 \leq i \leq N)$
• 入力は全て整数

入力

入力は以下の形式で標準入力で与えられる。

出力

$Q$ 行出力せよ。 $i$ 行目 $(1 \leq i \leq Q)$ には $i$ 番目のクエリに対する答えを出力せよ。

サンプル

5 2 3
1 2 3 4 5
4
1 5
2 4
3 3
2 5

4
1
0
2

$(1,2,3,4,5)$ の長さ $2$ の部分列のうち、総和が $3$ の倍数であるものは、 $(1,2)$ 、 $(1,5)$ 、 $(2,4)$ 、 $(4,5)$ の $4$ つなので、 $1$ 番目のクエリに対する答えは $4$ となります。

10 3 2
9 2 7 5 4 8 1 10 3 6
5
6 10
4 7
3 6
1 4
2 8

4
2
2
3
16