Ebi-chan has the FACTORIZATION MACHINE, which can factorize natural numbers M (greater than 1) in O($\log$ M) time! But unfortunately, the machine could display only digits and whitespaces.
In general, we consider the factorization of M as p_1^{e_1} \times p_2^{e_2} \times ... \times p_K^{e_K} where (1) i < j implies p_i < p_j and (2) p_i is prime. Now, she gives M to the machine, and the machine displays according to the following rules in ascending order with respect to i:
For example, if she gives either 22
or 2048
, then 2 11
is displayed. If either 24
or 54
, then 2 3 3
.
Okay, Ebi-chan has written down the output of the machine, but she notices that she has forgotten to write down the input! Now, your task is to count how many natural numbers result in a noted output. Note that Ebi-chan has mistaken writing and no input could result in the output.
The answer could be too large, so, you must output it modulo 10^9+7 (prime number).
N q_1 q_2 $\cdots$ q_N
In the first line, the number of the output of the machine is given. In the second line, the output of the machine is given.
Print the number of the natural numbers that result in the given output of the machine.
3 2 3 3
2
24 = 2^3 \times 3 and 54 = 2 \times 3^3 satisfy the condition.
3 2 3 4
1
Only 162 = 2 \times 3^4 satisfies the condition. Note that 4 is not prime.
3 3 5 2
1
Since 2 < 3 < 5, only 75 = 3 \times 5^2 satisfies the condition.
1 4
0
Ebi-chan should have written down it more carefully.