#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<ll, ll>
#define fi first
#define se second
ll x[500005], y[500005], n;
const ll mod = 1e9 + 7;
struct node{
ll s,e,m,val,lazy;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e)/2;
val = 0, lazy = 1;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
val = max(l->val, r->val);
}
else val = x[s];
}
void propo(){
if(lazy != 1){
val *= lazy;
val %= mod;
if(s != e)l->lazy *= lazy, r->lazy *= lazy, l->lazy %= mod, r->lazy %= mod;
lazy = 1;
}
}
void upd(int a, int b, int c){
if(s == a && e == b)lazy *= c, lazy %= mod;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b , c);
l->propo(), r->propo();
val = max(l->val, r->val);
}
}
int query(int p){
propo();
if(s == e)return val;
if(p <= m)return l->query(p);
else return r->query(p);
}
}*root;
ll expo(int a, int b, int c){
if(b == 1)return a;
if(b == 0)return 1;
ll t = expo(a, b/2, c);
t *= t, t %= c;
if(b%2)t *= a, t %= c;
return t;
}
struct node2{
ll s,e,m,val, pos;
node2 *l, *r;
node2(int _s, int _e){
s = _s, e = _e, m = (s + e)/2;
val = 0;
if(s != e){
l = new node2(s, m);
r = new node2(m+1, e);
if(l->val >= r->val)pos = l->pos;
else pos = r->pos;
val = max(l->val, r->val);
}
else val = y[s], pos = s;
}
void upd(int p, int v){
if(s == e)val = v;
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = max(l->val, r->val);
if(l->val >= r->val)pos = l->pos;
else pos = r->pos;
}
}
pi query(int a, int b){
if(a == s && b == e)return {val, pos};
else if(b <= m)return l->query(a, b);
else if(a > m)return r->query(a, b);
else return max(l->query(a, m), r->query(m+1, b));
}
}*root2;
set<int>s;
set<int> :: reverse_iterator it;
int answer(){
if(s.empty())return root2->query(1, n).fi;
it = s.rbegin();
ll cur = 0, prev = n, in = n;
while(cur <= 1e9 && it != s.rend()){
pi tmp = root2->query(*it, prev);
if(tmp.fi > cur)cur = tmp.fi, in = tmp.se;
cur *= x[*it];
prev = *it - 1;
it++;
if(it == s.rend()){
if(root2->query(1, prev + 1).fi > cur)in = root2->query(1, prev + 1).se;
}
}
return (root->query(in) * y[in]) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0;i<n;i++)x[i+1] = X[i], y[i+1] = Y[i];
root = new node(1, n);
for(int i=1;i<n;i++)root->upd(i+1, n, x[i]);
root2 = new node2(1, n);
for(int i=1;i<=n;i++)if(x[i] > 1)s.insert(i);
return answer();
}
int updateX(int pos, int val) {
pos++;
int tmp = x[pos];
if(tmp > 1)s.erase(pos);
if(val > 1)s.insert(pos);
x[pos] = val;
root->upd(pos, n, val);
root->upd(pos, n, expo(tmp, mod-2, mod));
return answer();
}
int updateY(int pos, int val) {
pos++;
root2->upd(pos, val);
y[pos] = val;
return answer();
}
