警告：添付ファイル内の trans.cpp が利用できないため、本問題は現時点では解決できません。

小 Bo は数列が大好きです。ある日、彼は偶然無限に続く数列を手に入れましたが、この数列には $N$ 個の項しか値が存在しないという特殊な性質がありました。小 Bo はこの数列を自分のノートパソコンに保存していましたが、不運にもある日画面をロックし忘れてしまいました。いたずら好きな子供が彼の数列を見つけ、悪戯をすることにしました。

その子供はまず数列 $A$ を新しい数列 $B$ にコピーし、その後 $t$ 回の操作を行いました。各操作では、$B$ を $A$ と $B$ の ディリクレ畳み込み の結果で更新しました。最後に、子供は新しい数列 $C$ を作成し、$B$ の第 $i$ 項を $C$ の第 $trans(i, M)$ 項に加算し、数列 $C$ を出力しました。

その時、小 Bo が突然戻ってきたため、子供は慌てて逃げ出し、$M$ が記録された紙を落としてしまいました。小 Bo はデスクトップ上に開くことのできないファイルがあることに気づきました。様々な手段を通じて、小 Bo は trans(i, M) の具体的なコードを入手しました。

今、小 Bo はこの数列 $C$ がどのようなものかを知りたいと考えていますが、$C$ は非常に長いため、$\sum_{i \geq 1} C_i \cdot i$ の値のみを知りたがっています。この結果を求める手助けをしてください。

添付ファイルには trans 関数を記述した trans.cpp が含まれています。

入力

1 行目に 3 つの整数 $N, m, t$ が与えられます。それぞれ、数列に値が存在する箇所の数、$M$ の異なる素因数の数、操作回数を表します。

続く $m$ 行には、それぞれ 2 つの正整数 $p_i, c_i$ が与えられます。ここで $M = \prod_{i=1}^{m} p_i^{c_i}$ です。

続く $N$ 行には、それぞれ 2 つの正整数 $a_i, b_i$ が与えられ、$A_{a_i} = b_i$ であることを示します。

出力

1 行で、答えを $1\,163\,962\,801$ で割った余りを出力してください。

入出力例

入出力例 1

3 1 1
3 1
2 5
5 3
6 1

出力例 1

729

注記

元の数列 $A$ において、$A_2 = 5$、$A_5 = 3$、$A_6 = 1$ です。

操作後の数列 $B$ は $B_4 = 25$、$B_{10} = 30$、$B_{12} = 10$、$B_{25} = 9$、$B_{30} = 6$、$B_{36} = 1$ となります。

$M = 3$ であり、$M$ の約数として利用可能なものは $3$ のみです。

$4, 10, 25$ は $trans$ を通しても値は変化せず、$trans(12, M) = 4$、$trans(30, M) = 10$、$trans(36, M) = 4$ となります。

したがって、最終的な数列 $C$ は $C_4 = 36, C_{10} = 36, C_{25} = 9$ となります。

答えは $36 \times 4 + 36 \times 10 + 9 \times 25 = 729$ です。

制約

本問題は合計 10 個のテストケースで構成され、各テストケースは 10 点です。

各データの特殊な性質については以下の表を参照してください。

すべてのデータにおいて以下が保証されます：

• $1 \leq N, m \leq 100000$
• $0 \leq t \leq 10^9$
• $1 \leq a_i, b_i \leq 10^9$
• $2 \leq p_i \leq 10^9$、データは $p_i, a_i$ が互いに異なり、$p_i$ が素数であることを保証する
• $1 \leq c_i \leq 20$、$\prod_{i=1}^{m} c_i \leq 10^5$