問題文

$F_0=0,\ \ F_1=1, \ \ F_i=F_{i-1}+F_{i-2}\ (i\geq2)$ により定められる数列$\{F_i\}$をフィボナッチ数列という。
フィボナッチ数列の$\bmod M$での周期を$10^9+7$で割った余りを求めよ。

入力

N
p_1 k_1
...
p_N k_N

$M$は素因数分解された形で与えられ、$M=\prod p_i^{k_i}$である。
$1\leq N\leq 1000$：整数
$2\leq p_i \leq 10^7$：素数であり、相異なる
$1\leq k_i \leq 1000$：整数

テストケースは全部で25個ある。
1smallから始まる7つのテストケースは$M\leq 10^7$を満たす（★2くらい）
2medから始まる9つのテストケースは$N\leq 20$かつ全ての$i$について$p_i\leq10^6,\ k_i=1$を満たす（★3くらい）
3largeから始まる9つのテストケースには追加制約はない（★4くらい）

出力

フィボナッチ数列の$\bmod M$での周期を$10^9+7$で割った余りを出力せよ。
ただし、「フィボナッチ数列$\{F_i\}$の$\bmod M$での周期」とは次の条件を満たすような正整数$n$のうち最小のものを指す。
条件：ある非負整数$A$が存在して、$A$以上の任意の整数$B$に対して$F_{B+n}=F_{B} \bmod M$が成り立つ

サンプル

2
2 2
3 1

24

2
97 1
103093 1

10103212

2
9999937 2
9999761 2

650542141