#include <bits/stdc++.h>
using namespace std;
#include "horses.h"
using ll = long long;
const ll MOD=1e9L+7LL;
int gn=0;
struct Value {
ll v;
bool m;
Value(ll vv, bool mm) : v(vv), m(mm) {}
Value(ll vv) : Value(vv, false) {}
Value() : Value(0LL, false) {}
Value operator*(const Value &o) {
ll prod=this->v*o.v;
bool modded=this->m||o.m||prod>=MOD;
prod%=MOD;
return Value(prod, modded);
}
bool operator>(const Value &o) {
if(this->m&&!o.m) return true;
if(o.m&&!this->m) return false;
assert(!this->m);
return this->v>o.v;
}
};
struct Node {
Value p1, p2, y;
Node(int xx, int yy) {
this->p1=Value(xx);
this->p2=Value(1);
this->y=Value(yy);
}
Node() {}
Node operator+(const Node &n) {
Node ans;
if(this->y>this->p2*n.p1*n.y) {
ans.p1=this->p1;
ans.p2=this->p2*n.p1*n.p2;
ans.y=this->y;
} else {
ans.p1=this->p1*this->p2*n.p1;
ans.p2=n.p2;
ans.y=n.y;
}
return ans;
}
};
#define MAXN 500500
int xs[MAXN], ys[MAXN];
Node seg[4*MAXN];
void build(int n, int l, int r) {
if(l==r) {
seg[n]=Node(xs[l], ys[l]);
} else {
int mid=(l+r)/2;
build(2*n, l, mid);
build(2*n+1, mid+1, r);
seg[n]=seg[2*n]+seg[2*n+1];
}
}
void update(int n, int l, int r, int i) {
if(l==r) seg[n]=Node(xs[i], ys[i]);
else {
int mid=(l+r)/2;
if(i<=mid) update(2*n, l, mid, i);
else update(2*n+1, mid+1, r, i);
seg[n]=seg[2*n]+seg[2*n+1];
}
}
int init(int N, int X[], int Y[]) {
for(int i=0;i<N;i++) xs[i]=X[i];
for(int i=0;i<N;i++) ys[i]=Y[i];
build(1, 0, N-1);
gn=N;
return (int)((seg[1].p1*seg[1].y).v);
}
int updateX(int pos, int val) {
xs[pos]=val;
update(1, 0, gn-1, pos);
return (int)((seg[1].p1*seg[1].y).v);
}
int updateY(int pos, int val) {
ys[pos]=val;
update(1, 0, gn-1, pos);
return (int)((seg[1].p1*seg[1].y).v);
}
