小 S は小 F と「斗地主」というゲームで遊んでいます。
かわいそうな小 S は、カードをプレイしても小 F に勝てないことに気付き、シャッフルの段階で細工をしようと考えました。
カードは全部で $n$ 枚あり、上から順に $1\sim n$ の番号が付いています。番号 $i$ のカードの点数は $f(i)$ です。この問題では、$f(i)$ は $f(i)=i$ または $f(i)=i^2$ のどちらか一方です。
シャッフルの方法は日常生活のものと似ています。以下、形式的に定義します。
シャッフルは合計 $m$ ラウンドからなり、順番に行われます。$i$ ラウンド目には、次の操作を行います。
- 小 S は上から $A_i$ 枚のカードを取り出します。これにより、カードは 2 つの山に分かれます。第 1 の山は上側の $A_i$ 枚、第 2 の山は残りの $n-A_i$ 枚です。それぞれの山の中の相対的な順序は変わりません。特に、$A_i=n$ または $A_i=0$ の場合、一方の山は空です。
- 次に、2 つの山を併合し、新たに第 3 の山を作ります。第 1 の山に残っているカードが $X$ 枚、第 2 の山に残っているカードが $Y$ 枚のとき、確率 $\frac{X}{X+Y}$ で第 1 の山の一番下のカードを取り出し、新しい第 3 の山の一番上に置きます。確率 $\frac{Y}{X+Y}$ で第 2 の山の一番下のカードを取り出し、新しい第 3 の山の一番上に置きます。
- 操作 2 を、両方の山が空になるまで繰り返します。これで 1 ラウンドのシャッフルが完了します。
シャッフルの過程はランダムなので、小 S には、ある位置にどのカードがあるのかを知ることができません。しかし、小 S は、$m$ ラウンドのシャッフルを終えた後の、ある位置のカードの点数の期待値を知りたいと思っています。小 S は、このような質問を合計 $Q$ 個します。
入力
ファイル landlords.in からデータを読み込んでください。
最初の行には、3 つの正整数 $n,m,type$ が与えられます。それぞれカードの枚数、シャッフルのラウンド数、$f(i)$ の種類を表します。$type=1$ のとき $f(i)=i$、$type=2$ のとき $f(i)=i^2$ です。
次の行には、$A_1\sim A_m$ を表す合計 $m$ 個の整数が与えられます。
次の行には、小 S の質問の個数を表す正整数 $Q$ が 1 つ与えられます。
続く $Q$ 行には、それぞれ正整数 $c_i$ が 1 つ与えられます。これは、小 S が上から $c_i$ 番目の位置のカードの点数の期待値を知りたいことを表します。$1\le c_i\le n$ が保証されます。
出力
ファイル landlords.out に出力してください。
合計 $Q$ 行出力してください。各行には、答えの法 $998244353$ における値を表す整数を 1 つ出力してください。
すなわち、答えを既約分数 $\frac{a}{b}$ で表し、$a$ と $b$ が互いに素であるとします。$bx\equiv a\pmod{998244353}$ かつ $0\le x<998244353$ を満たす整数 $x$ を出力してください。このような整数 $x$ は一意に存在することが証明できます。
入出力例
入力 1
4 1 1 3 1 1
出力 1
249561090
注記
確率 $\frac14$ で、上から順に並べた最終結果は $\{1,2,3,4\}$ となります。
確率 $\frac14$ で、上から順に並べた最終結果は $\{1,2,4,3\}$ となります。
確率 $\frac14$ で、上から順に並べた最終結果は $\{1,4,2,3\}$ となります。
確率 $\frac14$ で、上から順に並べた最終結果は $\{4,1,2,3\}$ となります。
したがって、最終的に最初の位置が $4$ である確率は $\frac14$、$1$ である確率は $\frac34$ です。よって、最初の位置の点数の期待値は $\frac74$ です。
シャッフルの過程をより直感的に理解できるように、結果が $\{1,4,2,3\}$ となる過程を下図に示します。
入出力例 2
選手用ディレクトリ内の landlords/landlords2.in と landlords/landlords2.ans を参照してください。
入出力例 3
選手用ディレクトリ内の landlords/landlords3.in と landlords/landlords3.ans を参照してください。
制約
すべてのテストケースについて、$3\le n\le 10^7,\ 1\le m,Q\le 5\times 10^5,\ 0\le A_i\le n,\ type\in\{1,2\}$ です。
各テストケースの詳しい制約は、次の表のとおりです。
| テストケース | $n$ | $m$ | $type=$ | その他の性質 |
|---|---|---|---|---|
| $1$ | $\le 10$ | $\le 1$ | $1$ | なし |
| $2$ | $\le 80$ | $\le 80$ | ||
| $3$ | $2$ | |||
| $4$ | $\le 100$ | $\le 5\times 10^5$ | すべての $A_i$ が同じ | |
| $5$ | $\le 10^7$ | $1$ | なし | |
| $6$ | ||||
| $7$ | ||||
| $8$ | $2$ | |||
| $9$ | ||||
| $10$ |
$Q\le n$ は保証されていないことに注意してください。
ここで、離散確率変数 $X$ の期待値 $\mathbb{E}[x]$ を定義します。
離散確率変数 $X$ が取り得る値を $X_1,X_2,\ldots,X_k$ とし、$\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ を、$X$ がそれぞれの値を取る確率とします。このとき、$X$ の期待値は次のとおりです。
$$ \mathbb{E}[x]=\sum_{i=1}^{k}X_i\Pr[X_i] $$