Problem Statement

The sequence $\{F_i\}$ defined by $F_0=0,\ \ F_1=1, \ \ F_i=F_{i-1}+F_{i-2}\ (i\geq2)$ is called the Fibonacci sequence.
Find the period of the Fibonacci sequence $\bmod M$, modulo $10^9+7$.

Input

N
p_1 k_1
...
p_N k_N

$M$ is given in prime-factorized form, where $M=\prod p_i^{k_i}$.
$1\leq N\leq 1000$: integer
$2\leq p_i \leq 10^7$: prime numbers, pairwise distinct
$1\leq k_i \leq 1000$: integer

There are 25 test cases in total.
The 7 test cases whose names start with 1small satisfy $M\leq 10^7$ (about ★2)
The 9 test cases whose names start with 2med satisfy $N\leq 20$ and, for all $i$, $p_i\leq10^6,\ k_i=1$ (about ★3)
The 9 test cases whose names start with 3large have no additional constraints (about ★4)

Output

Output the period of the Fibonacci sequence $\bmod M$, modulo $10^9+7$.
Here, "the period of the Fibonacci sequence $\{F_i\}$ $\bmod M$" refers to the smallest positive integer $n$ satisfying the following condition.
Condition: there exists a non-negative integer $A$ such that $F_{B+n}=F_{B} \bmod M$ holds for every integer $B$ greater than or equal to $A$

Sample

2
2 2
3 1

24

2
97 1
103093 1

10103212

2
9999937 2
9999761 2

650542141