EUREKA

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define NewVal vector<int>(46)
#define task "EUREKA"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 3e5 + 2;
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23,
               29, 31, 37, 41, 43, 47, 53, 59,
               61, 67, 71, 73, 79, 83, 89, 97,
               101, 103, 107, 109, 113, 127,
               131, 137, 139, 149, 151, 157,
               163, 167, 173, 179, 181, 191,
               193, 197, 199};
int n, a[N];
const ll mod = 123456789;
vector<int> s[202];

void Prepare()
{
    for (int i = 1; i <= 200; ++i)
    {
        s[i].resize(46, 0);
    }
    for (int i = 0; i < 46; ++i)
        for (int j = prime[i]; j <= 200; j += prime[i])
        {
            int v = j;
            while (v % prime[i] == 0)
            {
                v /= prime[i];
                ++s[j][i];
            }
        }
}

void Read()
{
    cin >> n;
    for (int i = 1; i <= 3 * n + 1; ++i)
        cin >> a[i];
}

vector<int> operator*(const vector<int> &a, const vector<int> &b)
{
    vector<int> ans(46);
    for (int i = 0; i < 46; ++i)
        ans[i] = a[i] + b[i];
    return ans;
}

vector<int> operator/(const vector<int> &a, const vector<int> &b)
{
    vector<int> ans(46);
    for (int i = 0; i < 46; ++i)
        ans[i] = a[i] - b[i];
    return ans;
}

vector<int> gcd(const vector<int> &a, const vector<int> &b)
{
    vector<int> ans(46);
    for (int i = 0; i < 46; ++i)
        ans[i] = min(a[i], b[i]);
    return ans;
}

ll Pow(ll a, int b)
{
    ll ans = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

void Solve()
{
    stack<vector<int>> st;
    for (int i = 3 * n + 1; i; --i)
    {
        if (a[i] == -1)
            st.push(NewVal);
        else
        {
            int y = a[i--],
                x = a[i];
            vector<int> p = st.top();
            st.pop();
            vector<int> q = st.top();
            st.pop();
            vector<int> d = gcd(p * s[x], q * s[y]),
                        tu = p * q;
            st.push(tu * s[x + y] / d);
        }
    }
    ll ans = 1;
    vector<int> cur = st.top();
    for (int i = 0; i < 46; ++i)
        ans = ans * Pow(prime[i], cur[i]) % mod;
    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Prepare();
    Read();
    Solve();
}