#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int N = 500000;
const int R = 710;
int n;
int* x;
int* y;
ll tree[4 * N];
int tree2[4 * N];
int tree3[4 * N];
void spMod(ll& num)
{
if (num >= mod)
{
num %= mod;
num += mod;
}
}
void ins(int i, int a, int b, int node)
{
if (a == b)
{
tree[node] = x[a];
tree2[node] = y[a];
if (x[a] == 1)
{
tree3[node] = 0;
} else
{
tree3[node] = 1;
}
return;
}
int mid = (a + b) / 2;
if (i <= mid) ins(i, a, mid, node * 2);
if (i > mid) ins(i, mid + 1, b, node * 2 + 1);
tree[node] = tree[node * 2] * tree[node *2 + 1];
tree2[node] = max(tree2[node * 2], tree2[node * 2 + 1]);
spMod(tree[node]);
tree3[node] = tree3[node *2] + tree3[node *2 +1];
}
ll getFac(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
return tree[node];
}
int mid = (a + b) / 2;
ll res = 1;
if (from <= mid) res *= getFac(from, to, a, mid, node * 2);
if (to > mid) res *= getFac(from, to, mid +1, b, node * 2 + 1);
spMod(res);
return res;
}
int getMax(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
return tree2[node];
}
int mid = (a + b) / 2;
int res = 0;
if (from <= mid) res = max(res, getMax(from, to, a, mid, node * 2));
if (to > mid) res = max(res, getMax(from, to, mid +1, b, node * 2 + 1));
return res;
}
void getKth(int k, int a, int b, int node, vector<int>& v)
{
if (a == b)
{
v.push_back(a);
return;
}
int mid = (a + b) / 2;
if (tree3[node * 2 + 1] > 0)
getKth(k, mid + 1, b, node * 2 + 1, v);
if (k - tree3[node * 2 + 1] < 0) return;
getKth(k - tree3[node * 2 + 1], a, mid, node * 2, v);
}
ll getBest()
{
int ci = -1;
ll cy = -1;
vector<int> v;
getKth(30, 0, n - 1, 1, v);
while (v.size() < 31) v.push_back(-1);
for (int i = 29; i >= 0; i--)
{
int cur = v[i];
int prev = v[i + 1];
if (cur == -1) continue;
ll ones = 0;
ll yVal = y[cur];
if (cur - prev > 1)
{
ones = getMax(prev + 1, cur - 1, 0, n - 1, 1);
}
if (ones > x[cur] * yVal)
{
cur--;
yVal = ones;
}
if (ci == -1)
{
ci = cur;
cy = yVal;
} else
{
ll fac = getFac(ci + 1, cur, 0, n - 1, 1);
fac *= yVal;
if (fac > cy)
{
cy = yVal;
ci = cur;
}
}
prev = cur;
}
int prev = v[0];
if (prev < n - 1)
{
ll yVal = getMax(prev + 1, n - 1, 0, n - 1, 1);
int cur = n - 1;
if (ci == -1)
{
cy = yVal;
ci = cur;
} else
{
ll fac = getFac(ci + 1, cur, 0, n - 1, 1);
fac *= yVal;
if (fac > cy)
{
cy = yVal;
ci = cur;
}
}
}
ll res = getFac(0, ci, 0, n - 1, 1);
res %= mod;
res *= cy;
res %= mod;
return res;
}
int init(int N, int X[], int Y[]) {
n = N;
x = X;
y = Y;
for (int i = 0; i < n; i++)
{
ins(i, 0, n - 1, 1);
}
//cout << best[0] << endl;
return getBest() % mod;
}
int updateX(int pos, int val) {
x[pos] = val;
ins(pos, 0, n - 1, 1);
return getBest() % mod;
}
int updateY(int pos, int val) {
y[pos] = val;
ins(pos, 0, n - 1, 1);
return getBest() % mod;
}
