//#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
const int maxn = 5e5+2;
const int mod = 1e9+7;
const ll inf = 1e9+10;
int n;
/// baraye Y --> tagir yek adad va maximom yek baze
int x[maxn], y[maxn];
struct segment_Y
{
int mx[maxn<<2];
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mx[v] = y[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v<<1, tl, tm);
build(v<<1|1, tm+1, tr);
mx[v] = max(mx[v<<1], mx[v<<1|1]);
}
void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mx[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) change(pos, val, v<<1, tl, tm);
else change(pos, val, v<<1|1, tm+1, tr);
mx[v] = max(mx[v<<1],mx[v<<1|1]);
}
int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > r) return 1;
if(tl == l && tr == r) return mx[v];
int tm = (tl + tr) >> 1;
return max(qu(l, min(tm,r), v<<1, tl, tm),
qu(max(tm+1,l), r, v<<1|1, tm+1, tr));
}
} seg_Y;
struct segment_X
{
int mul[maxn<<2];
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mul[v] = x[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v<<1, tl, tm);
build(v<<1|1, tm+1, tr);
mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
}
void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
mul[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) change(pos, val, v<<1, tl, tm);
else change(pos, val, v<<1|1, tm+1, tr);
mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
}
int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > r) return 1;
if(tl == l && tr == r) return mul[v];
int tm = (tl + tr) >> 1;
return (qu(l, min(tm,r), v<<1, tl, tm) * 1ll *
qu(max(tm+1,l), r, v<<1|1, tm+1, tr)) % mod;
}
} seg_X;
vector<int> seg[maxn<<2];
void buildX(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
if(x[tl] >= 2) seg[v].push_back(tl);
return;
}
int tm = (tl + tr) >> 1;
buildX(v<<1, tl, tm);
buildX(v<<1|1, tm+1, tr);
/// seg[v] nozolie
seg[v].clear();
for(auto x : seg[v<<1|1]) seg[v].push_back(x);
for(auto x : seg[v<<1]) seg[v].push_back(x);
while((int)seg[v].size() > 32ll) seg[v].pop_back();
}
void updX(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v].clear();
if(val >= 2) seg[v].push_back(tl);
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) updX(pos, val, v<<1, tl, tm);
else updX(pos, val, v<<1|1, tm+1, tr);
/// seg[v] nozolie
seg[v].clear();
for(auto x : seg[v<<1|1])
{
if((int)seg[v].size() > 30) break;
seg[v].push_back(x);
}
for(auto x : seg[v<<1])
{
if((int)seg[v].size() > 30) break;
seg[v].push_back(x);
}
}
int mul(int a, int b) {return min(a*1ll*b,inf);}
int mult[33][33];
vector<int> X,Y;
bool cmp(int i, int j)
{
bool sw = 0;
if(i > j) {sw = 1; swap(i,j);}
return (sw ^ (Y[i] < mul(mult[i+1][j],Y[j])));
}
int answer()
{
vector<int> ve = seg[1];
bool DO = 0;
if(ve.empty()) DO = 1;
else if(ve.back() > 1) DO = 1;
if(DO) ve.push_back(1);
reverse(ve.begin(), ve.end());
X.clear(); Y.clear();
vector<int> YES;
for(int i = 0; i < (int)ve.size(); i++)
{
X.push_back(x[ve[i]]);
Y.push_back(seg_Y.qu(ve[i],n));
YES.push_back(i);
}
for(int i = 0; i < 33; i++) for(int j = 0; j < 33; j++) mult[i][j] = 1;
for(int l = 0; l < (int)X.size(); l++)
{
mult[l][l] = X[l];
for(int r = l+1; r < (int)X.size(); r++)
mult[l][r] = mul(mult[l][r-1],X[r]);
}
sort(YES.begin(), YES.end(), cmp);
int id = ve[YES.back()];
return (seg_X.qu(1,id) * 1ll * Y[YES.back()]) % mod;
}
int init(int N, int X[], int Y[])
{
n = N;
x[0] = 1; y[0] = 0;
for(int i = 1; i <= n; i++)
{
x[i] = X[i-1];
y[i] = Y[i-1];
}
seg_X.build();
seg_Y.build();
buildX();
return answer();
}
int updateX(int pos, int val)
{
pos++;
x[pos] = val;
updX(pos,val);
seg_X.change(pos,val);
return answer();
}
int updateY(int pos, int val)
{
pos++;
y[pos] = val;
seg_Y.change(pos,val);
return answer();
}
/*
int arrX[3] = {2,1,3};
int arrY[3] = {3,4,1};
signed main()
{
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<< init(3, arrX, arrY) <<"\n";
cout<< updateY(1,2) <<"\n";
}
*/
