#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int OFF=(1<<19);
const int MAXN=5e5+5;
int n;
pii T[2*OFF];
int Tmax[2*OFF];
int x[MAXN], y[MAXN];
int mul(int a, int b) {
return (ll)a*b%MOD;
}
pii mrg(pii a, pii b) {
pii ret=mp(mul(a.X, b.X), a.Y || b.Y);
ret.Y|=((ll)ret.X!=(ll)a.X*b.X);
return ret;
}
int nadji(int val, int pos=1) {
if (pos>=OFF) return pos-OFF;
if (T[pos*2+1].Y || (!T[pos*2+1].Y && T[pos*2+1].X>=val)) return nadji(val, pos*2+1);
return nadji(val/T[pos*2+1].X+!!(val%T[pos*2+1].X), pos*2);
}
int query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
if (lo>=a && hi<=b) return T[pos].X;
if (lo>=b || hi<=a) return 1;
int mid=(lo+hi)/2;
return mul(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
}
int answer() {
int ind=-1;
if (T[1].Y) ind=nadji(MOD);
// printf("ind: %d\n", ind);
ll ret=0, curr=1;
for (int i=ind+1; i<n; ++i) {
curr*=x[i];
ret=max(ret, curr*y[i]);
}
// printf("ret: %lld, query: %d\n", ret);
return mul(ret%MOD, query(0, ind+1));
}
int init(int N, int XX[], int YY[]) {
n=N;
for (int i=0; i<n; ++i) x[i]=XX[i], y[i]=YY[i];
fill(T, T+2*OFF, mp(1, 0));
memset(Tmax, 0, sizeof Tmax);
for (int i=0; i<n; ++i) T[OFF+i].X=x[i], Tmax[OFF+i]=y[i];
for (int i=OFF-1; i>0; --i) T[i]=mrg(T[i*2], T[i*2+1]), Tmax[i]=max(Tmax[i*2], Tmax[i*2+1]);
return answer();
}
int updateX(int pos, int val) {
x[pos]=val;
pos+=OFF;
T[pos].X=val;
pos/=2;
while (pos) {
T[pos]=mrg(T[pos*2], T[pos*2+1]);
pos/=2;
}
return answer();
}
int updateY(int pos, int val) {
y[pos]=val;
pos+=OFF;
Tmax[pos]=val;
pos/=2;
while (pos) {
Tmax[pos]=max(Tmax[pos*2], Tmax[pos*2+1]);
pos/=2;
}
return answer();
}
