#include "horses.h"
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int n;
const int NN = 1e6+5;
const ll mod = 1e9+7;
ll a[NN];
ll b[NN];
//=============================================
ll binpow(ll p, ll q){
if(q == 0)return 1ll;
ll temp = binpow(p, q/2);
temp *= temp;
temp %= mod;
if(q%2==1)temp *= p;
return temp%mod;
}ll inver(ll p){
return binpow(p, mod-2);
}//===============================================
struct Node {
ld sum;
ll mul;
};
Node neutral = {0., 1ll};
int sz;
vector<Node> t;
vector<Node> ans;
Node combine(Node f, Node s){
return {f.sum+s.sum, (f.mul*s.mul)%mod};
}
Node mx(Node f, Node s){
if(f.sum > s.sum)return f;
else return s;
}
void build(){
sz=1;
while(sz<n)sz<<=1;
t.assign(sz*2, neutral);
ans.assign(sz*2, neutral);
for(int i=0;i<n;i++){
t[i+sz].sum = log2(a[i]);
t[i+sz].mul = a[i];
}for(int i=1;i<sz;i++){
t[i+sz].sum += t[i+sz-1].sum;
t[i+sz].mul *= t[i+sz-1].mul;t[i+sz].mul%=mod;
}for(int i=0;i<sz;i++){
ans[i+sz].sum = t[i+sz].sum+log2(b[i]);
ans[i+sz].mul =(t[i+sz].mul*b[i])%mod;
}for(int i=sz-1;i>0;i--){
ans[i] = mx(ans[i*2], ans[i*2+1]);
}
}
Node getpref(int i){
ld ansd = 0.;
ll ansl = 1;
for(i+=sz; i>0; i>>=1){
ansd += t[i].sum;
ansl *= t[i].mul;ansl%=mod;
}return {ansd, ansl};
}
void push(int L, int R, int node){
if(R-L == 1)return;
t[node*2] = combine(t[node], t[node*2]);
t[node*2+1]=combine(t[node], t[node*2+1]);
ans[node*2] = combine(ans[node*2], t[node]);
ans[node*2+1]=combine(ans[node*2+1], t[node]);
t[node] = neutral;
ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyX(int l, int r, int L, int R, Node val, int node){
if(L >= r || R <= l)return;
push(L, R, node);
if(L >= l && R <= r){
t[node] = combine(t[node], val);
ans[node]=combine(ans[node], val);
return;
}int mid = (L+R)/2;
modifyX(l, r, L, mid, val, node*2);
modifyX(l, r, mid, R, val, node*2+1);
ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyY(int pos, int L, int R, Node val, int node){
if(R-L == 1){
ans[node] = val;
return;
}int mid = (L+R)/2;
push(L, R, node);
if(mid <= pos){
modifyY(pos, mid, R, val, node*2+1);
}else {
modifyY(pos, L, mid, val, node*2);
}ans[node] = mx(ans[node*2], ans[node*2+1]);
}//===============================================
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0;i<n;i++)a[i] = X[i];
for(int i=0;i<n;i++)b[i] = Y[i];
build();
return ans[1].mul;
}
int updateX(int pos, int val) {
// Node X = getpref(pos);
modifyX(pos, sz, 0, sz, {log2(val)-log2(a[pos]), ((val*inver(a[pos]))%mod)}, 1);
a[pos] = val;
return ans[1].mul;
}
int updateY(int pos, int val) {
Node X = getpref(pos);
modifyY(pos, 0, sz, {X.sum+log2(val), (X.mul*val)%mod}, 1);
b[pos] = val;
return ans[1].mul;
}
