#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
class RangeMax {
public:
vector<long long> dat; int size_ = 1;
void init(int sz) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int pos, int x) {
pos += size_; dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return 0LL;
long long s1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long s2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return max(s1, s2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 30; i++) {
if ((b & (1LL << i)) != 0) { p *= q; p %= m; }
q *= q; q %= m;
}
return p;
}
long long INV(long long x) {
return modpow(x, mod - 2, mod);
}
set<pair<int, long long>>S; RangeMax Z;
long long NN, A[500009], B[500009], TotalSum = 1;
long long calculate() {
auto itr = S.end(); long long L = 1; vector<pair<long long, long long>> vec;
while (itr != S.begin()) {
itr--;
pair<int, long long> E = (*itr);
long long D = Z.query(1LL * E.first, NN + 1);
//cout << "[" << E.first << ", " << NN + 1 << "] = " << D << endl;
vec.push_back(make_pair(D, L));
L *= E.second; if (L > (1LL << 30)) break;
}
if (L <= (1LL << 30)) vec.push_back(make_pair(Z.query(0, NN + 1), L));
/*cout << "vec : " << endl;
for (int i = 0; i < vec.size(); i++) cout << vec[i].first << " / " << vec[i].second << endl;
cout << endl;*/
long long maxn = 0;
for (int i = 0; i < (int)vec.size(); i++) {
maxn = max(maxn, 1LL * vec[i].first * (vec[vec.size() - 1].second / vec[i].second));
}
maxn %= mod;
long long s1 = TotalSum;
if ((int)vec.size() >= 1) { s1 *= INV(vec[vec.size() - 1].second); s1 %= mod; }
return maxn * s1 % mod;
}
int init(int N, int X[], int Y[]) {
NN = N; Z.init(NN + 2);
for (int i = 0; i < N; i++) { A[i] = X[i]; B[i] = Y[i]; }
for (int i = 0; i < N; i++) {
Z.update(i, B[i]); TotalSum *= (1LL * A[i]); TotalSum %= mod;
if (A[i] != 1) S.insert(make_pair(i, A[i]));
}
return calculate();
}
int updateX(int i, int val) {
TotalSum *= INV(A[i]); TotalSum %= mod; if (A[i] != 1) S.erase(make_pair(i, A[i]));
A[i] = val;
TotalSum *= A[i]; TotalSum %= mod; if (A[i] != 1) S.insert(make_pair(i, A[i]));
return calculate();
}
int updateY(int pos, int val) {
Z.update(pos, val);
return calculate();
}
