#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e12;
const long long MOD = 1e9 + 7;
long long sq(long long num) { return num * num; }
long long mod_pow(long long x, long long n) {
  if (n == 0) return 1;
  if (n == 1) return x % MOD;
  long long res = sq(mod_pow(x, n / 2));
  res %= MOD;
  if (n % 2 == 1) {
    res *= x;
    res %= MOD;
  }
  return res;
}
long long mod_add(long long a, long long b) { return (a + b) % MOD; }
long long mod_sub(long long a, long long b) { return (a - b + MOD) % MOD; }
long long mod_mul(long long a, long long b) { return a * b % MOD; }
long long n;
long long a[100100];
long long dp[2][1001000];
map<long long, long long> id;
bool used[1001000];
vector<int> prime;
bool is_prime[1001000];
int sieve(int n) {
  int p = 0;
  for (int i = 0; i <= n; i++) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime.push_back(i);
      id[i] = prime.size() - 1;
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = 0;
    }
  }
  return p;
}
int main() {
  sieve(1001000);
  cin >> n;
  for (int i = 0; i < (n); i++) cin >> a[i];
  if (!is_prime[a[0]])
    cout << 0 << endl;
  else {
    dp[0][0] = 1;
    for (int i = (1); i < (n); i++) {
      if (is_prime[a[i]]) {
        if (i > 1 && a[i] > a[i - 2])
          dp[0][i] = (dp[0][i] + dp[1][i - 1]) % MOD;
        if (a[i] > a[i - 1]) dp[0][i] = (dp[0][i] + dp[0][i - 1]) % MOD;
        if (is_prime[a[i - 1]]) dp[1][i] = (dp[1][i] + dp[0][i - 1]) % MOD;
      } else {
        if (is_prime[a[i - 1]]) dp[1][i] = (dp[1][i] + dp[0][i - 1]) % MOD;
      }
    }
    for (int i = 0; i < (n); i++) cout << dp[0][i] << " ";
    cout << endl;
    for (int i = 0; i < (n); i++) cout << dp[1][i] << " ";
    cout << endl;
    cout << mod_add(dp[0][n - 1], dp[1][n - 1]) << endl;
  }
}
