#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define fir first
#define sec second
const int MM = 1e9+7;
pair< pair<ll,ll>, ll> segtree[200000];
int nn, Y[500010];
pair<pair<ll,ll>,ll> combine(pair<pair<ll,ll>,ll> a, pair<pair<ll,ll>,ll> b)
{
pair<pair<ll,ll>,ll> x;
x.fir.fir = (a.fir.fir%MM)*(b.fir.fir%MM), x.fir.fir%=MM;
if(a.fir.sec>b.fir.sec) x.fir.fir = a.fir.fir%MM, x.fir.sec = (x.fir.fir%MM)*(a.fir.sec%MM), x.fir.sec%=MM, x.sec = a.sec;
else x.fir.sec = (x.fir.fir%MM)*(b.fir.sec%MM), x.fir.sec%=MM, x.sec = b.sec;
return x;
}
void build(int p, int l, int r, int x[], int y[])
{
if(l==r) segtree[p] = mp(mp(x[l],y[l]), l);
else{
int mid = (l+r)/2;
build(p*2, l, mid, x, y);
build(p*2+1, mid+1, r, x, y);
segtree[p] = combine(segtree[p*2], segtree[p*2+1]);
}
}
void update(int p, int l, int r, int pos, ll val, bool x)
{
if(l==r){
if(x) segtree[p].fir.fir = val;
else segtree[p].fir.sec = val;
return;
}
int mid = (l+r)/2;
if(pos<=mid) update(p*2, l, mid, pos, val, x);
else update(p*2+1, mid+1, r, pos, val, x);
segtree[p] = combine(segtree[p*2], segtree[p*2+1]);
}
int query(int p, int L, int R, int l, int r)
{
if(l>r)return 1ll;
if(L>=l and R<=r) return segtree[p].fir.fir;
int mid = (L+R)/2;
int left = query(p*2, L, mid, l, min(r,mid));
int right = query(p*2+1, mid+1, R, max(mid+1, l), r);
int ans = (left%MM)*(right%MM);
return ans%MM;
}
int init(int n, int x[], int y[])
{
nn = n;
for(int i = 0; i < n; i++) Y[i] = y[i];
build(1, 0, n-1, x, y);
int ind = segtree[1].sec;
/*for(int i = 1; i < 4*nn; i++)
cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
cout << ind << "\n\n";*/
return query(1, 0, n-1, 0, ind)*Y[ind];
}
int updateX(int pos, int val)
{
update(1, 0, nn-1, pos, (ll)val, true);
int ind = segtree[1].sec;
/*for(int i = 1; i < 4*nn; i++)
cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
cout << ind << "\n\n";*/
return query(1, 0, nn-1, 0, ind)*Y[ind];
}
int updateY(int pos, int val)
{
Y[pos] = val;
update(1, 0, nn-1, pos, val, false);
int ind = segtree[1].sec;
/*for(int i = 1; i < 4*nn; i++)
cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
cout << ind << "\n\n";*/
return query(1, 0, nn-1, 0, ind)*Y[ind];
}
