問題文

整数列 $(a_i)_{i \geq 0}$ の最初の $K$ 項 $a_0,\dots, a_{K-1}$ と，$K$ 個の整数 $c_1, \dots,c_K$ が与えられます． $(a_i)_{i \geq 0}$ の第 $K$ 項以降を，以下の漸化式で定めます:

• $\displaystyle a_i = \sum_{k=1}^K c_k a_{i-k} \quad (i \geq K)$．

長さ $N$ の配列 $(x_0, \dots, x_{N-1})$ の全要素を $0$ に初期化し，以下の操作 $j = 1,\dots, M$ を，操作 $1$ から順に行います:

• $($操作 $j)$:$\quad l_j \leq i < r_j$ なる各整数 $i$ に対し，$x_i \gets x_i + a_{i-l_j}$ と更新する．

各整数 $i$ $(0 \leq i < N)$ に対し，全ての操作の後の $x_i$ の値を $10^9 + 7$ で割った余りを求めてください．

入力

入力は以下の形式で与えられる:

$K \quad N \quad M$
$a_0 \quad a_1 \quad \cdots \quad a_{K-1}$
$c_1 \quad c_2 \quad \cdots \quad c_K$
$l_1 \quad r_1$
$l_2 \quad r_2$
$\ \vdots$
$l_M \quad r_M$

• 入力は全て整数
• $1 \leq K \leq 200$
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq a_i \leq 10^9 \quad (0 \leq i < K)$
• $0 \leq c_i \leq 10^9 \quad (1 \leq i \leq K)$
• $0 \leq l_j < r_j \leq N \quad (1 \leq j \leq M)$

出力

$(i+1)$ 行目 $(0 \leq i < N)$ に，全ての操作の後の $x_i$ の値を $10^9 + 7$ で割った余りを出力せよ． 最後に改行を出力すること．

サンプル

2 6 3
3 1
1 2
2 4
0 5
3 6

3
1
10
13
24
7

4 10 6
38357 29371 11020 79402
86940 11636 45261 69281
2 8
1 9
5 6
2 7
0 6
3 10

38357
67728
117105
187521
18341484
711694633
729776525
364121460
472238231
652635015