#pragma GCC optimize ("O3")
#pragma comment(linker , "/STACK:102400000,102400000")
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxN = 500000 + 10;
const LL mod = 1000000007LL;
struct Segt {
static Segt *pmem , mem[maxN<<2];
Segt *lc , *rc;
int l , r;
LL x;
double log_x , log_y;
Segt() {}
Segt(int l0 , int r0) : l(l0) , r(r0) , x(1LL) , log_x(0.0) , log_y(0.0) {}
} Segt::mem[maxN<<2] , *Segt::pmem = Segt::mem;
Segt *tr;
LL Y[maxN];
int best_ans_pos;
double best_log_ans;
Segt* build(int l , int r) {
Segt *tr = new (Segt::pmem++) Segt(l , r);
if(l != r) {
int m = (l+r)/2;
tr->lc = build(l , m);
tr->rc = build(m+1 , r);
}
return tr;
}
void modify_x(Segt *tr , int p , LL x) {
int l = tr->l , r = tr->r;
int m = (l+r)/2;
if(l == r) {
tr->x = x;
tr->log_x = log(static_cast<double>(x));
return;
}
if(p <= m) modify_x(tr->lc , p , x);
else modify_x(tr->rc , p , x);
tr->x = (tr->lc->x*tr->rc->x)%mod;
tr->log_x = tr->lc->log_x+tr->rc->log_x;
}
void modify_y(Segt *tr , int p , LL y) {
int l = tr->l , r = tr->r;
int m = (l+r)/2;
if(l == r) {
tr->log_y = log(static_cast<double>(y));
return;
}
if(p <= m) modify_y(tr->lc , p , y);
else modify_y(tr->rc , p , y);
tr->log_y = max(tr->lc->log_y , tr->rc->log_y);
}
void query_best_ans_pos(Segt *tr , double tmp) {
if(tr->l == tr->r) {
if(tmp+tr->log_x+tr->log_y > best_log_ans) {
best_log_ans = tmp+tr->log_x+tr->log_y;
best_ans_pos = tr->l;
}
return;
}
query_best_ans_pos(tr->rc , tmp+tr->lc->log_x);
if(tmp+tr->lc->log_x+tr->lc->log_y > best_log_ans) query_best_ans_pos(tr->lc , tmp);
}
LL query_x(Segt *tr , int p) {
int l = tr->l , r = tr->r;
int m = (l+r)/2;
LL res;
if(r <= p) return tr->x;
res = query_x(tr->lc , p);
if(m+1 <= p) (res *= query_x(tr->rc , p)) %= mod;
return res;
}
int init(int N , int x[] , int y[]) {
tr = build(0 , N-1);
for(int i = 0; i < N; i++) modify_x(tr , i , x[i]);
for(int i = 0; i < N; i++) {
Y[i] = static_cast<LL>(y[i]);
modify_y(tr , i , Y[i]);
}
best_ans_pos = 0;
best_log_ans = 0.0;
query_best_ans_pos(tr , 0.0);
return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}
int updateX(int pos , int val) {
modify_x(tr , pos , static_cast<LL>(val));
best_ans_pos = 0;
best_log_ans = 0.0;
query_best_ans_pos(tr , 0.0);
return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}
int updateY(int pos , int val) {
Y[pos] = static_cast<LL>(val);
modify_y(tr , pos , Y[pos]);
best_ans_pos = 0;
best_log_ans = 0.0;
query_best_ans_pos(tr , 0.0);
return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}
