時間制限 : sec, メモリ制限 : KB
English / Japanese  

D: 素因数分解の多様性 (The Diversity of Prime Factorization)

問題

えびちゃんは素因数分解マシンの不良品を持っています。この機械は、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 から順に以下のように出力を行います。全ての数字はスペース区切りで表示されます。

  • e_i = 1 ならば p_i を出力する
  • e_i > 1 ならば p_i e_i を出力する

たとえば、222048 を与えると 2 11 と表示され、2454 を与えると 2 3 3 と表示されます。

さて、えびちゃんは表示された素因数分解をメモしておいたのですが、与えた自然数をメモしておくのを忘れていたことに気づきました。素因数分解のメモが与えられるので、元の自然数としてありえるものがいくつあるかを求めてください。ただし、メモが間違っていて、条件を満たす自然数が一つも存在しないこともあります。

また、その個数は非常に大きくなる場合があるので、10^9+7 (素数) で割ったあまりを出力してください。

入力形式

N
q_1 q_2 $\cdots$ q_N

1 行目には、表示された整数の個数 N が与えられます。 2 行目には、表示された N 個の整数がスペース区切りで与えられます。

制約

  • 1 \leq N \leq 10^5
  • 2 \leq q_i \leq 10^6 (1 \leq i \leq N)

出力形式

マシンに与えると q_1 q_2 $\cdots$ q_N を表示するような自然数の個数を 10^9+7 で割ったあまりを出力してください。

入力例1

3
2 3 3

出力例1

2

2^3 \times 3 = 242 \times 3^3 = 54 が考えられます。

入力例2

3
2 3 4

出力例2

1

2 \times 3^4 = 162 に定まります。4 は素数ではないことに注意してください。

入力例3

3
3 5 2

出力例3

1

2<3<5 なので、3 \times 5^2 = 75 に定まります。

入力例4

1
4

出力例4

0

えびちゃんはもっと考えてメモを取るべきです。

Note

Link