#include "horses.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define ll long long
const ll M=1e9+7;
const int N=5e5+5;
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
int n;
int a[N];
int b[N];
struct pii
{
ll vl=1;
double vi=0;
};
pii lz[4*N];
struct node
{
double mx=0;
int pos=-1;
ll pr=1;
};
ll bp(ll x,ll y){
x%=M;
if (y==0)return 1;
if (y==1)return x;
ll r=bp(x*x,y/2);
if (y%2)r*=x;
return r%M;
}
ll inv(ll x){
return bp(x,M-2);
}
node seg[4*N];
node join(node x,node y){
node r;
r.mx=max(x.mx,y.mx);
if (r.mx==x.mx)r.pos=x.pos;
if (r.mx==y.mx)r.pos=y.pos;
r.pr=(x.pr*y.pr)%M;
return r;
}
void build(int s=0,int e=n,int v=1){
if (e-s==1){
seg[v].pos=s;
seg[v].mx=log2(a[s]);
seg[v].pr=a[s];
return;
}
int li=2*v;
int ri=2*v+1;
int m=(s+e)/2;
build(s,m,li);
build(m,e,ri);
seg[v]=join(seg[li],seg[ri]);
}
void lazy(int v,int f){
ll x=lz[v].vl;
lz[v].vl=1;
seg[v].pr=(seg[v].pr*x)%M;
double y=lz[v].vi;
lz[v].vi=0;
seg[v].mx+=y;
if (f!=1){
lz[2*v].vl=(lz[2*v].vl*x)%M;
lz[2*v+1].vl=(lz[2*v+1].vl*x)%M;
lz[2*v].vi+=y;
lz[2*v+1].vi+=y;
}
}
void update(int l,int r,int x,int s=0,int e=n,int v=1){
lazy(v,e-s);
if (l>=e or r<=s)return;
if (l<=s and e<=r){
lz[v].vl=(lz[v].vl*x)%M;
lz[v].vi+=log2(x);
lazy(v,e-s);
return;
}
int li=2*v;
int ri=2*v+1;
int m=(s+e)/2;
update(l,r,x,s,m,li);
update(l,r,x,m,e,ri);
seg[v]=join(seg[li],seg[ri]);
}
void update1(int l,int r,int x,int s=0,int e=n,int v=1){
lazy(v,e-s);
if (l>=e or r<=s)return;
if (l<=s and e<=r){
lz[v].vl=(lz[v].vl*inv(x))%M;
lz[v].vi-=log2(x);
lazy(v,e-s);
return;
}
int li=2*v;
int ri=2*v+1;
int m=(s+e)/2;
update1(l,r,x,s,m,li);
update1(l,r,x,m,e,ri);
seg[v]=join(seg[li],seg[ri]);
}
node query(int l,int r,int s=0,int e=n,int v=1){
lazy(v,e-s);
if (l>=e or r<=s)return node();
if (l<=s and e<=r)return seg[v];
int li=2*v;
int ri=2*v+1;
int m=(s+e)/2;
node p=join(query(l,r,s,m,li),query(l,r,m,e,ri));
seg[v]=join(seg[li],seg[ri]);
return p;
}
int init(int K,int x[],int y[]){
n=K;
for (int i=0;i<4*N;i++){
lz[i].vl=1;
}
for (int i=0;i<n;i++){
a[i]=y[i];
}
for (int i=0;i<n;i++){
b[i]=x[i];
}
build();
for (int i=0;i<n;i++){
update(i,n,x[i]);
}
int po=query(0,n).pos;
return query(po,po+1).pr;
}
int updateX(int i,int x){
update1(i,n,b[i]);
b[i]=x;
update(i,n,b[i]);
int po=query(0,n).pos;
return query(po,po+1).pr;
}
int updateY(int i,int x){
update1(i,i+1,a[i]);
a[i]=x;
update(i,i+1,a[i]);
int po=query(0,n).pos;
return query(po,po+1).pr;
}
