注意

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

問題文

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

制約

• $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$は互いに相異なる 素数
• $E_i = 1$
• 入力はすべて整数

入力

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

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

出力

答えを出力せよ。

入出力例

5 2 3
1
3
1

1

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

99824 4 353
1
353
1

305

$\binom{99824}{4} = 4137162004755731876$です。
これを$353$で割った余りは$305$です。

9982 4 4353
2
3 1451
1 1

585

$\binom{9982}{4} = 413426150188485$です。
これを$4353$で割った余りは$585$です。

1234 567 890
3
2 5 89
1 1 1

450

$\binom{1234}{567} ≈ 1.1668 × 10^{368}$です。
これを$890$で割った余りは$450$です。

12345678 9012345 9699690
8
2 3 5 7 11 13 17 19
1 1 1 1 1 1 1 1

0

$\binom{12345678}{9012345} ≈ 7.5152 × 10^{3127231}$です。
これを$9699690$で割った余りは$0$です。
本問題では、$E_i = 1$が保証される点に注意してください。