えびちゃんは素因数分解マシンの不良品を持っています。この機械は、2 以上の自然数 M を与えると O($\log$ M) でその素因数分解を行ってくれますが、困ったことに数字以外を表示できないバグがありました。
一般に、M の素因数分解が p_1^{e_1} \times p_2^{e_2} \times ... \times p_K^{e_K} (ただし i<j ならば p_i<p_j、また各 p_i は素数) の場合を考えます。M を与えると、この機械は i = 1 から順に以下のように出力を行います。全ての数字はスペース区切りで表示されます。
たとえば、22
や 2048
を与えると 2 11
と表示され、24
や 54
を与えると 2 3 3
と表示されます。
さて、えびちゃんは表示された素因数分解をメモしておいたのですが、与えた自然数をメモしておくのを忘れていたことに気づきました。素因数分解のメモが与えられるので、元の自然数としてありえるものがいくつあるかを求めてください。ただし、メモが間違っていて、条件を満たす自然数が一つも存在しないこともあります。
また、その個数は非常に大きくなる場合があるので、10^9+7 (素数) で割ったあまりを出力してください。
N q_1 q_2 $\cdots$ q_N
1 行目には、表示された整数の個数 N が与えられます。 2 行目には、表示された N 個の整数がスペース区切りで与えられます。
マシンに与えると q_1 q_2 $\cdots$ q_N を表示するような自然数の個数を 10^9+7 で割ったあまりを出力してください。
3 2 3 3
2
2^3 \times 3 = 24、2 \times 3^3 = 54 が考えられます。
3 2 3 4
1
2 \times 3^4 = 162 に定まります。4 は素数ではないことに注意してください。
3 3 5 2
1
2<3<5 なので、3 \times 5^2 = 75 に定まります。
1 4
0
えびちゃんはもっと考えてメモを取るべきです。