注意

本問題は 制約強化版 です。
$E_i = 1$とした簡易版は別に出題します。

問題文

二項係数$\binom{N}{R}$を$M$で割った余りを求めてください。
ここで、$M = \prod_{i=1}^C P_i ^ {E_i}$と素因数分解できることが保証されます。

制約

• $1 \leq R \leq N \leq 10^{18}$
• $2 \leq M \leq 10^7$
• $M = \prod_{i=1}^C P_i ^ {E_i}$
• $1 \leq C$
• $2 \leq P_1 < P_2 < ･･･ < P_C$
• $P_i$は互いに相異なる 素数
• $1 \leq E_i$
• 入力はすべて整数

入力

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

$N$ $R$ $M$
$C$
$P_1$ $P_2$ ･･･ $P_C$
$E_1$ $E_2$ ･･･ $E_C$

出力

答えを出力せよ。

入出力例

5 2 4
1
2
2

2

$\binom{5}{2} = 10$です。
これを$4$で割った余りは$2$です。

55 22 44
2
2 11
2 1

21

$\binom{55}{22} = 1300853625660225$です。
これを$44$で割った余りは$21$です。

57 29 777787
1
777787
1

724783

$\binom{57}{29} = 15033633249770520$です。
これを$777787$で割った余りは$724783$です。

31415 92 65
2
5 13
1 1

35

$\binom{31415}{92} ≈ 3.8364 × 10^{271}$です。
これを$65$で割った余りは$35$です。

12345679 777777 720720
6
2 3 5 7 11 13
4 2 1 1 1 1

665280

$\binom{12345679}{777777} ≈ 4.1512 × 10^{1260755}$です。
これを$720720$で割った余りは$665280$です。