#include "horses.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
ll fastexp(ll a,ll e)
{
if(e==0) {return 1LL;}
if(e%2LL==0)
{
ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod;
}
else
{
ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod;
}
}
ll inv(ll s) //assumes mod is prime
{
return fastexp(s,mod-2LL);
}
class ST1
{
public:
ll N;
class SV //seg value
{
public:
ld a; ll pos;
SV() {a=-((ld) INF);}
SV(ld x) {a=x;}
SV operator & (SV X)
{
SV ANS(max(a,X.a));
if(a>X.a) {ANS.pos=pos;} else {ANS.pos=X.pos;}
return ANS;
}
};
class LV //lazy value
{
public:
ld a;
LV() {a=0.0;}
LV(ld x) {a=x;}
LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
};
SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
{
SV X(p[c].a+lazy[c].a); X.pos=p[c].pos;
return X;
}
SV neuts; LV neutl;
vector<SV> p;
vector<LV> lazy;
vector<pl> range;
ST1() {N=0LL;}
ST1(vector<ld> arr)
{
N = (ll) 1<<(ll) ceil(log2(arr.size()));
REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
REP(i,0,N) {p.pb(neuts);}
REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i); p[i+N].pos=i;}
REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i); p[i+N].pos=i;}
ll cur = N-1;
while(cur>0)
{
p[cur]=p[2*cur]&p[2*cur+1];
range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
cur--;
}
REP(i,0,2*N) {lazy.pb(neutl);}
}
void prop(ll c) //how lazy values propagate
{
lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
lazy[c]=neutl;
}
SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(c);}
prop(c);
p[c]=upval(c);
SV ans = query(a,b,2*c)&query(a,b,2*c+1);
return ans;
}
void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return ;}
if(x>=a && y<=b)
{
lazy[c]=s&lazy[c];
return;
}
prop(c);
update(s,a,b,2*c); update(s,a,b,2*c+1);
p[c]=upval(2*c)&upval(2*c+1);
}
};
class ST2
{
public:
ll N;
class SV //seg value
{
public:
ll a;
SV() {a=1LL;}
SV(ll x) {a=x;}
SV operator & (SV X) {SV ANS((a*X.a)%mod); return ANS;}
};
class LV //lazy value
{
public:
ll a;
LV() {a=1LL;}
LV(ll x) {a=x;}
LV operator & (LV X) {LV ANS((a*X.a)%mod); return ANS;}
};
SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
{
SV X((p[c].a*fastexp(lazy[c].a,(range[c].ss-range[c].ff+1)))%mod);
return X;
}
SV neuts; LV neutl;
vector<SV> p;
vector<LV> lazy;
vector<pl> range;
ST2() {N=0LL;}
ST2(vector<ll> arr)
{
N = (ll) 1<<(ll) ceil(log2(arr.size()));
REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
REP(i,0,N) {p.pb(neuts);}
REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
ll cur = N-1;
while(cur>0)
{
p[cur]=p[2*cur]&p[2*cur+1];
range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
cur--;
}
REP(i,0,2*N) {lazy.pb(neutl);}
}
void prop(ll c) //how lazy values propagate
{
lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
lazy[c]=neutl;
}
SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(c);}
prop(c);
p[c]=upval(c);
SV ans = query(a,b,2*c)&query(a,b,2*c+1);
return ans;
}
void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
{
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return ;}
if(x>=a && y<=b)
{
lazy[c]=s&lazy[c];
return;
}
prop(c);
update(s,a,b,2*c); update(s,a,b,2*c+1);
p[c]=upval(2*c)&upval(2*c+1);
}
};
ll N;
vector<ld> ps;
vector<ll> X; vector<ll> Y;
ST1 A; ST2 B;
int solve()
{
ll ind = A.query(0,N-1).pos;
ll ans = B.query(0,ind).a;
ans*=Y[ind]; ans%=mod; if(ans<0LL) {ans+=mod;}
int x = (int) ans;
return x;
}
int init(int n, int x[], int y[])
{
N=(ll) n;
REP(i,0,N) {X.pb((ll) x[i]); Y.pb((ll) y[i]);}
vector<ld> ps; ld sum=(ld) 0.0;
ld val1,val2;
REP(i,0,N)
{
val1 = (ld) log2((ld) X[i]);
val2 = (ld) log2((ld) Y[i]);
sum+=val1;
ps.pb(sum+val2);
}
ST1 initA(ps); A=initA;
ST2 initB(X); B=initB;
return solve();
}
int updateX(int pos, int v)
{
ll newX = (ll) v; ll oldX = X[pos]; X[pos]=newX;
ll val1 = (newX*inv(oldX))%mod;
B.update(val1,pos,pos);
ld val2 = (ld) log2((ld) newX) - (ld) log2((ld) oldX);
A.update(val2,pos,N-1);
return solve();
}
int updateY(int pos, int v)
{
ll oldY = Y[pos]; ll newY = (ll) v; Y[pos] = newY;
ld val = (ld) log2((ld) newY) - (ld) log2((ld) oldY);
A.update(val,pos,pos);
return solve();
}
