正二十面体（正二十面体）は、合計 $20$ 個の面、$12$ 個の頂点、$30$ 本の辺を持っています。以下に図を示します。

岐艾（ギアイ）は正二十面体を手に入れ、各面を $3n-3$ 本の線で切り分け、$n^2$ 個の互いに合同な正三角形に分割しました。例えば、下の図は $n=2$ の場合です。

現在、この正二十面体には合計 $20n^2$ 個の小さな三角形が存在します。岐艾は $k$ 種類の色の塗料を持っています。彼女はこれらの三角形を塗り分け、第 $i$ 種類の色の三角形が $a_i$ 個になるようにしたいと考えています。

さらに、同じ種類の色であっても、塗料の価格は異なります。第 $i$ 種類の色について、価格が $0, 1, \dots, b_i$ である塗料がそれぞれ $1$ つずつ存在します。価格 $c$ の塗料とは、それを使って三角形を $1$ つ塗るごとに $c$ 円の費用がかかることを意味します。同じ種類の色であっても、塗り分けの過程で異なる価格の塗料を任意に使用することができます。

岐艾は現在 $m$ 円の予算を持っています。彼女は、$0 \le j \le m$ のそれぞれについて、ちょうど $j$ 円かかる塗り方の総数が何通りあるかを知りたいと考えています。

正二十面体を回転させて一致する塗り方は、同一の塗り方とみなします。注意：岐艾は専門家であるため、各三角形に塗られた塗料の価格も識別可能です。

入力

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

$n \ m \ k$ $a_1 \ b_1$ $a_2 \ b_2$ $\vdots$ $a_k \ b_k$

出力

$j$ 円かかる塗り方の総数を $f(j)$ としたとき、以下の値を計算して出力せよ。

$$ \bigoplus_{j=0}^m ((f(j) \bmod 998244353) + j) $$

入出力例

入力 1

1 100 1
20 1

出力 1

3554

注記 1

デコード前のデータは以下の通りである：

$$ f(0,\dots,10) = [1, 1, 6, 21, 96, 262, 681, 1302, 2157, 2806, 3158] $$

また、$f(j)=f(20-j)$ であり、$j>20$ の範囲では $f(j)=0$ である。

入力 2

1 100 2
9 3
11 2

出力 2

870

入力 3

2 100 2
36 3
44 2

出力 3

788814413

入力 4

2 100000 2
36 233
44 666

出力 4

953441426

制約

すべてのデータセットにおいて、以下を満たす。

• $1\le n\le 7\times 10^3$
• $0\le m\le 5\times 10^6$
• $1\le k\le 5$
• $1\le a_i$
• $\sum_i a_i = 20n^2$
• $0\le b_i\le m$