#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
int pct(int x) { return __builtin_popcount(x); }
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
unsyncIO();
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct mi {
typedef decay<decltype(MOD)>::type T;
/// don't silently convert to T
T v; explicit operator T() const { return v; }
mi() { v = 0; }
mi(ll _v) {
v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
if (v < 0) v += MOD;
}
friend bool operator==(const mi& a, const mi& b) {
return a.v == b.v; }
friend bool operator!=(const mi& a, const mi& b) {
return !(a == b); }
friend bool operator<(const mi& a, const mi& b) {
return a.v < b.v; }
mi& operator+=(const mi& m) {
if ((v += m.v) >= MOD) v -= MOD;
return *this; }
mi& operator-=(const mi& m) {
if ((v -= m.v) < 0) v += MOD;
return *this; }
mi& operator*=(const mi& m) {
v = (ll)v*m.v%MOD; return *this; }
mi& operator/=(const mi& m) { return (*this) *= inv(m); }
friend mi pow(mi a, ll p) {
mi ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend mi inv(const mi& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mi operator-() const { return mi(-v); }
mi& operator++() { return *this += 1; }
mi& operator--() { return *this -= 1; }
friend mi operator+(mi a, const mi& b) { return a += b; }
friend mi operator-(mi a, const mi& b) { return a -= b; }
friend mi operator*(mi a, const mi& b) { return a *= b; }
friend mi operator/(mi a, const mi& b) { return a /= b; }
};
typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;
vector<vmi> comb;
void genComb(int SZ) {
comb.assign(SZ,vmi(SZ)); comb[0][0] = 1;
FOR(i,1,SZ) F0R(j,i+1)
comb[i][j] = comb[i-1][j]+(j?comb[i-1][j-1]:0);
}
template<class T> struct MaxSeg { // comb(ID,b) = b
const T ID = mp(0, 0); T comb(T a, T b) { return max(a, b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // sum on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
template<class T> struct ProdSeg { // comb(ID,b) = b
const T ID = mi(1); T comb(T a, T b) { return a*b; }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // sum on interval [l, r]
if(l > r) return 1;
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
const int mx = 500005;
int N;
ll X[mx];
ll Y[mx];
MaxSeg<pair<ll, int>> mseg; //value, index of Y[]
ProdSeg<mi> pseg; //X values
set<int> n1pos; //positions of non 1 X values
const ll MAXVAL = ll(MOD);
int query(){
//ps("QUERY");
if(sz(n1pos) == 0){
return int(mseg.query(0, N-1).f);
}
ll curprod = 1;
auto it = n1pos.end();
while(curprod <= ll(MAXVAL)){
if(it == n1pos.begin()){
break;
}
it = prev(it);
int ind = *it;
curprod*=X[ind];
}
pair<ll, mi> curans = mp(0, 0);
pair<ll, int> q;
if(it == n1pos.begin()){
int ind = *it;
if(ind != 0){
q = mseg.query(0, ind-1);
ckmax(curans, mp(q.f, pseg.query(0, q.s)*mi(q.f)));
}
curprod = 1;
while(it != n1pos.end()){
int r;
if(next(it) == n1pos.end()){
r = N;
}
else{
r = *(next(it));
}
curprod*=X[*it];
q = mseg.query(*it, r-1);
ckmax(curans, mp(curprod*q.f, pseg.query(0, q.s)*mi(q.f)));
//ps(*it, curprod, q.f);
it = next(it);
}
return int(curans.s);
}
else{
curprod = 1;
auto it2 = it;
while(it != n1pos.end()){
if(it != it2) curprod*=X[*it];
int r;
if(next(it) == n1pos.end()){
r = N;
}
else{
r = *(next(it));
}
q = mseg.query(*it, r-1);
//cout << *it << " " << q.f << " " << q.s << " " << curprod*q.f << " " << int(pseg.query(0, q.s)*mi(q.f)) << "\n";
ckmax(curans, mp(curprod*q.f, pseg.query(0, q.s)*mi(q.f)));
it = next(it);
}
return int(curans.s);
}
}
int init(int _N, int x[], int y[]) {
N = _N;
for(int i = 0; i < N; i++){
X[i] = x[i];
Y[i] = y[i];
}
mseg.init(N+5);
pseg.init(N+5);
for(int i = 0; i < N; i++){
mseg.upd(i, mp(Y[i], i));
pseg.upd(i, mi(X[i]));
if(X[i] != 1) n1pos.insert(i);
}
return query();
}
int updateX(int pos, int val) {
if(X[pos] != 1) n1pos.erase(pos);
pseg.upd(pos, mi(val));
X[pos] = val;
if(X[pos] != 1) n1pos.ins(pos);
return query();
}
int updateY(int pos, int val) {
//ps(pos, val);
mseg.upd(pos, mp(ll(val), pos));
Y[pos] = val;
return query();
}
