#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, t[40];
ll x[500005], y[500005], bit[500005];
pll seg[2000005];
set <int> s;
void build(int id, int l, int r) {
if (l == r) {
seg[id] = {y[l], l};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
if (seg[id * 2 + 1].fi == max(seg[id * 2].fi, seg[id * 2 + 1].fi)) seg[id] = seg[id * 2 + 1];
else seg[id] = seg[id * 2];
}
void point_update(int id, int l, int r, int pos) {
if (l == r) {
seg[id] = {y[l], l};
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) point_update(id * 2, l, mid, pos);
else point_update(id * 2 + 1, mid + 1, r, pos);
if (seg[id * 2 + 1].fi == max(seg[id * 2].fi, seg[id * 2 + 1].fi)) seg[id] = seg[id * 2 + 1];
else seg[id] = seg[id * 2];
}
pll range_max(int id, int l, int r, int lq, int rq) {
if (lq > r || rq < l) return {0, -1};
if (lq <= l && r <= rq) return seg[id];
int mid = (l + r) >> 1;
pll L = range_max(id * 2, l, mid, lq, rq);
pll R = range_max(id * 2 + 1, mid + 1, r, lq, rq);
if (R.fi >= L.fi) return R;
return L;
}
ll p(ll b, ll x) {
if (x == 0) return 1;
if (x == 1) return b % mod;
ll tmp = p(b, x/2);
if (x % 2 == 0) return tmp * tmp % mod;
return (tmp * tmp) % mod * b % mod;
}
void update(int x, ll val) {
for (x; x <= n; x += (x&(-x))) {
bit[x] = bit[x] * val % mod;
}
}
ll query(int x) {
ll ret = 1;
for (x; x > 0; x -= (x&(-x))) {
ret = ret * bit[x] % mod;
}
return ret;
}
int calc(int pos) {
ll ret = query(pos) * y[pos] % mod;
return ret;
}
int solve() {
int cur = 31;
for (auto it = s.rbegin(); it != s.rend(); it++) {
t[cur] = *it;
cur--;
if (cur < 0) break;
}
pll p = range_max(1, 1, n, 1, n);
int bestpos = p.se;
ll prod = 1;
FOR(i, cur + 1, 31) {
if (t[i] <= bestpos) continue;
prod *= x[t[i]];
if (prod > y[bestpos]) {
bestpos = t[i];
prod = 1;
}
ll required = y[bestpos] / prod + 1;
pll res = range_max(1, 1, n, t[i], n);
if (res.fi >= required) {
bestpos = res.se;
prod = 1;
}
}
//cout << bestpos << endl;
return calc(bestpos);
}
int init(int N, int X[], int Y[]) {
n = N;
FOR(i, 0, n-1) {
x[i + 1] = X[i];
y[i + 1] = Y[i];
bit[i + 1] = 1;
}
FOR(i, 1, n) {
update(i, x[i]);
if (x[i] > 1) s.insert(i);
}
build(1, 1, n);
return solve();
}
int updateX(int pos, int val) {
pos++;
ll mul = 1LL * val * p(x[pos], mod - 2) % mod;
update(pos, mul);
if (x[pos] == 1 && val > 1) {
s.insert(pos);
} else if (x[pos] > 1 && val == 1) {
s.erase(pos);
}
x[pos] = val;
return solve();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
point_update(1, 1, n, pos);
return solve();
}
