#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
const ll INF = 1e18+10;
const ll MOD = 1e9+7;
const ll MX_VAL = 1e9;
struct stnode {
ll prod,mx;
stnode (){ prod = 1; mx = 0; }
stnode merge_node (const stnode& rhs){
stnode res;
res.prod = prod*rhs.prod; res.prod %= MOD;
res.mx = max(mx,rhs.mx);
return res;
}
};
ll modpow (ll b, ll e){
ll res = 1;
while (e > 0){
if (e%2) res *= b;
e /= 2; b *= b;
res %= MOD; b %= MOD;
}
return res;
}
struct frac {
ll n,d;
frac(){ n = 1; d = 1;}
frac (ll _n, ll _d){
n = _n; d = _d;
}
bool operator>(const frac& rhs) const{
return n*rhs.d > rhs.n*d;
}
bool operator<(const frac& rhs) const{
return n*rhs.d < rhs.n*d;
}
ll mult (ll x){
x *= n; x %= MOD;
x *= modpow(d,MOD-2); x %= MOD;
return x;
}
};
class SegTree {
private:
vector<stnode> st;
ll n;
vi a,b;
ll left(ll x){ return (x << 1); }
ll right(ll x){ return ((x << 1) + 1); }
void build (ll i, ll l, ll r){
if (l == r){
st[i].prod = a[i];
st[i].mx = b[i];
}else{
ll m = (l+r)/2;
build(left(i),l,m);
build(right(i),m+1,r);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
stnode query (ll i, ll l, ll r, ll ql, ll qr){
if (qr >= r && l >= ql){
return st[i];
}else if (l > qr || ql > r){
return stnode();
}else{
ll m = (l+r)/2;
stnode lres = query(left(i),l,m,ql,qr);
stnode rres = query(right(i),m+1,r,ql,qr);
return lres.merge_node(rres);
}
}
void update (ll i, ll l, ll r, ll type, ll val, ll idx){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r >= idx && idx >= l){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r == l){
if (type == 0) st[i].prod = val;
else st[i].mx = val;
}else{
ll m = (l+r)/2;
update(left(i),l,m,type,val,idx);
update(right(i),m+1,r,type,val,idx);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
}
public:
SegTree (vi _a, vi _b): a(_a), b(_b){
n = a.size();
st.resize(4*n);
build(1,0,n-1);
}
SegTree(ll _n){
n = _n;
a.assign(n,1);
b.assign(n,0);
st.assign(4*n,stnode());
}
SegTree(){}
ll query (ll type, ll l, ll r){
stnode res;
//cout << "queried: " << type << " " << l << " " << r << endl;
if (r >= l) res = query(1,0,n-1,l,r);
if (type == 0) return res.prod;
else return res.mx;
}
void update (ll type, ll val, ll idx){
//cout << "update: " << type << " " << val << " " << idx << endl;
//cout << n << endl;
update (1,0,n-1,type,val,idx);
}
};
class WeirdDS {
private:
SegTree st;
vi x,y;
set<ll> overone;
ll n;
public:
WeirdDS(int _n){
n = _n;
st = SegTree(n);
x.assign(n,1);
y.assign(n,0);
set<ll>().swap(overone);
overone.insert(0);
}
WeirdDS(){}
void updateX(ll pos, ll val){
st.update(0,val,pos);
if (val == 1){
auto itr = overone.find(-pos);
if (itr != overone.end())
overone.erase(itr);
}else{
overone.insert(-pos);
}
overone.insert(0);
x[pos] = val;
}
void updateY(ll pos, ll val){
st.update(1,val,pos);
}
ll query (){
bool broke = false;
ll prv = n;
ll ctr = 1;
frac maxMult;
for (auto i: overone){
ll bigY = st.query(1,-i,prv-1);
frac curMult = frac(bigY,ctr);
if (curMult > maxMult) maxMult = curMult;
prv = -i;
ctr *= x[-i];
if (x[-i] == 1 && i != 0) return INF;
if (ctr > MX_VAL) break;
}
return maxMult.mult(st.query(0,0,n-1));
}
};
WeirdDS myDS;
int init(int n, int x[], int y[]) {
//cout.setstate(ios_base::failbit);
myDS = WeirdDS(n);
for (ll i = 0; n > i; i++){
myDS.updateX(i,x[i]);
myDS.updateY(i,y[i]);
}
////cout << myDS.query() << endl;
return myDS.query();
}
int updateX(int pos, int val) {
//cout << "updateX: " << pos << " " << val << endl;
myDS.updateX(pos,val);
//cout << res << endl;
return myDS.query();
}
int updateY(int pos, int val) {
//cout << "updateY: " << pos << " " << val << endl;
myDS.updateY(pos,val);
//cout << res << endl;
return myDS.query();
}
