// SmartCoder
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  // Including tree_order_statistics_node_update

using namespace __gnu_pbds;
using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
#define minei(x) min_element(x.begin(), x.end()) - (x).begin()
#define maxei(x) max_element(x.begin(), x.end()) - (x).begin()
#define LSOne(S) (S & (-S))

#define uns(v) sort((v).begin(), (v).end()), v.erase(unique(v.begin(), v.end()), v.end())
#define acusum(x) accumulate(x.begin(), x.end(), 0)
#define acumul(x) accumulate(x.begin(), x.end(), 1, multiplies<int>());
#define bits(x) __builtin_popcount(x)
#define oo INT_MAX
#define inf 1000000000
#define MAXN 1000007
#define MOD 1000000007

const double pi = acos(-1.0);
const double eps = 1e-11;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

void pv(vector<int> v) {
    if (v.empty()) return;
    cout << v[0];
    for (int i = 1; i < sz(v); i++) {
        cout << " " << v[i];
    }
    cout << endl;
}

void _solve(vector<int> v) {
    int n = sz(v);
    set<int> st;
    for (int i = 0; i < n; i++) {
        int num = v[i];
        for (int j = 2; j <= num; j++) {
            while (num % j == 0) {
                st.insert(j);
                num /= j;
            }
        }
        if (num != 1) st.insert(num);
    }
    vector<ll> primes(all(st));
    n = sz(primes);
    vector<ll> res;
    for (int i = 0; i < (1 << n); i++) {
        ll cur = 1;
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) cur *= primes[j];
        }
        bool valid = true;
        for (int j = 0; j < sz(v) && valid; j++) {
            if (__gcd(v[j] * 1ll, cur) == 1) valid = false;
        }

        if (valid) {
            res.pb(cur);
        }
    }
    sort(all(res));
    cout << res[0] << "\n";
}
int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    _solve(v);

    return 0;
}

#include <bits/stdc++.h>

int mod = 1e9 + 7;

int main(){
    int N;
    std::string Caa, Cab, Cba, Cbb;
    std::cin >> N >> Caa >> Cab >> Cba >> Cbb;
    
    std::map< std::string, int > cur;
    std::map< std::string, int > next;
    cur["AB"] = 1;
    
    for(int i=2; i<5; i++){
        for(auto itr=cur.begin(); itr!=cur.end(); itr++){
            std::string cur_str = itr->first;
            for(int j=0; j<cur_str.size()-1; j++){
                std::string next_str = cur_str;
                if(next_str[j] == 'A' && next_str[j+1] == 'A'){
                    next_str.insert(j+1, Caa);
                }else if(next_str[j] == 'A' && next_str[j+1] == 'B'){
                    next_str.insert(j+1, Cab);
                }else if(next_str[j] == 'B' && next_str[j+1] == 'A'){
                    next_str.insert(j+1, Cba);
                }else{
                    next_str.insert(j+1, Cbb);
                }
                next[next_str] = 1;
            }
        }
        cur = next;
        next.clear();
    }
    
    if(cur.size() == 1){
        std::cout << 1 << std::endl;
    }else if(cur.size() == 4){
        long long ans = 1;
        for(int i=3; i<N; i++){
            ans = (ans * 2) % mod;
        }
        std::cout << ans << std::endl;
    }else{
        std::vector< long long > ans(N+1);
        ans[0] = 0; ans[1] = 0; ans[2] = 1;
        for(int i=3; i<=N; i++){
            ans[i] = (ans[i-1] + ans[i-2]) % mod;
        }
        std::cout << ans[N] << std::endl;
    }
    
    return 0;
}

