問題
もけちゃんは子供たちの遊び道具としてボールを購入することにしました。
このお店には $N$ 色のボールが販売されています。
色 $i$ $(1 \leq i \leq N)$ のボールは $A_i$ 個用意されており、色 $i$ のボールにはそれぞれ、$1$ 以上 $A_i$ 以下の番号が重複なくつけられています。
もけちゃんはこれらすべてのボール、すなわち $\sum_{i=1}^{N} A_i$ 個のボールを購入しました。
そして、購入したすべてのボールを、一つの箱に入れておきました。
知的好奇心旺盛なもけちゃんは、ふと次の値が気になりました。
- 任意の個数のボールを箱の中から取り出したとき、ボールの色が $L$ 種類以上 $R$ 種類以下存在するような取り出し方の総数。
しかし、残念ながらもけちゃんにはこの値を求めることができませんでした。
$Q$ 回にわたって、$L_j, R_j$ $(1 \leq j \leq Q)$ が入力として与えられるので、任意の個数のボールを箱の中から取り出したとき、ボールの色が $L_j$ 種類以上 $R_j$ 種類以下存在するような取り出し方の総数を、もけちゃんの代わりにそれぞれ求めてください。
ただし、答えは非常に大きくなる場合があるので、$998244353$ で割った余りを出力してください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
出力
出力は $Q$ 行からなる。
各整数 $j$ について、答えを $998244353$ で割った余りを $j$ 行目に出力せよ。
各出力の末尾には改行を入れること。
制約
- $1 \leq N \leq 5,000$
- $1 \leq A_i \leq 1,000,000$
- $1 \leq Q \leq 1,000,000$
- $1 \leq L_j \leq R_j \leq N$
- 入力はすべて整数である。
入出力例
入力例１
3 2 3 1 6 1 1 2 2 3 3 1 2 2 3 1 3
出力例１
11 31 21 42 52 63
$L_1 = 1, R_1 = 1$ なので、任意の個数のボールを箱の中から取り出したとき、ボールの色が $1$ 種類となるような取り出し方の総数を求めます。
ここで、それぞれのボールの色を $X, Y, Z$ と表し、それぞれのボールを $X_1, X_2, Y_1, Y_2, Y_3, Z_1$ と表すことにします。
条件を満たすボールの取り出し方は、$\{X_1\}, \{X_2\}, \{Y_1\}, \{Y_2\}, \{Y_3\}, \{Z_1\}, \{X_1, X_2\}, \{Y_1, Y_2\}, \{Y_2, Y_3\}, \{Y_1, Y_3\}, \{Y_1, Y_2, Y_3\}$ の $11$ 通り考えられます。
入力例２
19 161 211 242 221 171 116 798 411 507 253 293 693 917 277 943 21 300 45 938 4 5 15 13 15 16 17 8 18
出力例２
575131170 22149484 909410410 293118148
答えを $998244353$ で割った余りを出力してください。