Range Count Subsequence Query

2 secs 1024 MB
momoyuu's icon momoyuu

問題文

整数 KKDD 、および長さ NN の非負整数列 (a1,a2,,aN)(a_1, a_2, \ldots, a_N) が与えられます。

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

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

注意

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

制約

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

入力

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

NNKKDD
a1a_1a2a_2\ldotsaNa_N
QQ
l1l_1r1r_1
l2l_2r2r_2
\vdots
lQl_QrQr_Q

出力

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

サンプル

入力例1
5 2 3
1 2 3 4 5
4
1 5
2 4
3 3
2 5
出力例1
4
1
0
2

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

入力例2
10 3 2
9 2 7 5 4 8 1 10 3 6
5
6 10
4 7
3 6
1 4
2 8
出力例2
4
2
2
3
16

提出


Go (1.21)