Range Count Subsequence Query

整数 、 、および長さ の非負整数列 が与えられます。

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

• 番目のクエリでは整数 が与えられます。非負整数列 の長さ の部分列のうち、総和が の倍数であるものの個数を で割ったあまりを求めてください。

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

• 入力は全て整数

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

行出力せよ。 行目 には 番目のクエリに対する答えを出力せよ。

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

4
1
0
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

4
2
2
3
16