Problem:

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

Problem

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:

 If e_i = 1, then displays p_i,

 otherwise, displays p_i e_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).

Input

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.

Constraints

 1 \leq N \leq 10^5

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

Output

Print the number of the natural numbers that result in the given output of the machine.

Sample Input 1

3
2 3 3

Sample Output for Input 1

2

24 = 2^3 \times 3 and 54 = 2 \times 3^3 satisfy the condition.

Sample Input 2

3
2 3 4

Sample Output 2 for Input 2

1

Only 162 = 2 \times 3^4 satisfies the condition.  Note that 4 is not prime.

Sample Input 3

3
3 5 2

Sample Output for Input 3

1

Since 2 < 3 < 5, only 75 = 3 \times 5^2 satisfies the condition.

Sample Input 4

1
4

Sample Output for Input 4

0

Ebi-chan should have written down it more carefully.



Sample input:
3
2 3 3


Sample output:
2

Submission status: Accepted

Solution code:
from collections import defaultdict
MAX = 1000000
ROOT = 1000
MOD = 1000000007
is_prime = [True] * (MAX + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, ROOT + 1):
  if is_prime[i]:
    for j in range(i * i, MAX + 1, i):
      is_prime[j] = False

n = int(input())
qlst = list(map(int, input().split()))
total1 = 0#next is kisuu or sisuu
total2 = 1#next is kisuu only(pre is index)
last_prime = 0
dic = {}
dic[(last_prime, 0)] = total1
dic[(last_prime, 1)] = total2
for q in qlst:
  new_dic = defaultdict(int)
  for k, v in dic.items():
    last_prime, t = k
    if is_prime[q]:
      if t == 0:
        if last_prime < q:
          new_dic[(q, 0)] = (new_dic[(q, 0)] + v) % MOD
          new_dic[(last_prime, 1)] = (new_dic[(last_prime, 1)] + v) % MOD
        else:
          new_dic[(last_prime, 1)] = (new_dic[(last_prime, 1)] + v) % MOD
      else:
        if last_prime < q:
          new_dic[(q, 0)] = (new_dic[(q, 0)] + v) % MOD
    
    if not is_prime[q]:
      if t == 0:
        new_dic[(last_prime, 1)] = (new_dic[(last_prime, 1)] + v) % MOD
  dic = new_dic
print(sum(dic.values()) % MOD)

Submission status: Runtime Error

Solution code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
    static void Main()
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Program().Solve();
        Console.Out.Flush();
    }
    Scanner cin = new Scanner();
    int mod = 1000000007;

    void Solve()
    {
        int N = cin.Nextint;
        var Q = cin.Scanint;
        eratos(Q.Max());
        var B = new int[N];
        //B[i]=1 素数, B[i]=-1 素数でない B[i] = 0どちらでもいい
        if (!is_prime[Q[0]])
        {
            Console.WriteLine(0);
            return;
        }

        int min_prime = Q[0];
        B[0] = 1;
        for (int i = 1; i < N; i++)
        {
            if (Q[i] <= min_prime || !is_prime[Q[i]])
            {
                B[i] = -1;
                B[i - 1] = 1;
                min_prime = Q[i - 1];
                if (i < N - 1)
                {
                    B[i + 1] = 1;
                    min_prime = Q[i + 1];
                    i++;
                }
            }

            if (3 <= i && Q[i - 2] == Q[i - 1] && Q[i - 1] == Q[i])
            {
                B[i - 3] = 1;
                B[i - 2] = 0;
                B[i - 1] = 1;
                B[i] = 0;
                min_prime = Q[i - 1];
                if (i < N - 1)
                {
                    B[i + 1] = 1;
                    min_prime = Q[i + 1];
                    i++;
                }
            }

        }


        long zero = 1; int zero_prime = 0;
        long one = 0; int one_prime = 0;

        for (int i = 0; i < N; i++)
        {
            if (one == 0 && (!is_prime[Q[i]] || Q[i] < zero_prime))
            {
                Console.WriteLine(0);
                return;
            }

            if (B[i] == 1)
            {
                if (one_prime < Q[i])
                {
                    long tmp = one;
                    one = (zero + one) % mod;
                    zero = 0;
                    zero_prime = 0;
                    one_prime = Q[i];
                }
                else if (zero_prime < Q[i])
                {
                    long tmp = one;
                    one = zero;
                    zero = 0;
                    zero_prime = 0;
                    one_prime = Q[i];
                }
            }
            else if (B[i] == -1)
            {
                zero = one;
                one = 0;
                one_prime = 0;
            }
            else if (is_prime[Q[i]])
            {            
                //oneの後に0を置くとき、zero_primeはone_primeになる
                if (one_prime < Q[i])
                {
                    long tmp = one;
                    one = (zero + one) % mod;
                    zero = tmp;
                    zero_prime = one_prime;
                    one_prime = Q[i];
                }
                else if (zero_prime < Q[i]) 
                {
                    long tmp = one;
                    one = zero;
                    zero = tmp;
                    zero_prime = one_prime;
                    one_prime = Q[i];
                }
                else
                {
                    zero = one;
                    one = 0;
                    one_prime = 0;
                }
            }
            else
            {
                zero = one;
                one = 0;
                one_prime = 0;
            }
            //Console.WriteLine(one + " " + zero);
        }




        Console.WriteLine((one + zero) % mod);

    }



    List<int> prime;
    bool[] is_prime;
    void eratos(int n)
    {
        prime = new List<int>();
        is_prime = new bool[n + 1];
        for (int i = 0; i <= n; i++) is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;
        for (int i = 0; i <= n; i++)
        {
            if (is_prime[i])
            {
                prime.Add(i);
                for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
            }
        }
    }
    int[] P;
    void phi(int n)
    {
        P = new int[n + 1];
        for (int i = 0; i <= n; i++) P[i] = i;
        for (int i = 2; i <= n; i++)
        {
            if (is_prime[i])
            {
                P[i] -= P[i] / i;
                for (int j = 2 * i; j <= n; j += i) P[j] -= P[j] / i;
            }
        }
    }
}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] Scan { get { return Console.ReadLine().Split(); } }
    public int[] Scanint { get { return Array.ConvertAll(Scan, int.Parse); } }
    public long[] Scanlong { get { return Array.ConvertAll(Scan, long.Parse); } }
    public double[] Scandouble { get { return Array.ConvertAll(Scan, double.Parse); } }
    public string Next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return Next;
        }
    }
    public int Nextint { get { return int.Parse(Next); } }
    public long Nextlong { get { return long.Parse(Next); } }
    public double Nextdouble { get { return double.Parse(Next); } }
}