#include "horses.h"
#include "bits/stdc++.h"

using ll = long long;
using i128 = __int128;
using namespace std;

struct mint {
	static constexpr int mod = 1e9 + 7;

	int data = 0;

	mint() = default;
	mint(int data) : data(data) {}

	mint operator+(const mint &other) const {
		int res = data + other.data;
		if (res >= mod) {
			res -= mod;
		}
		return res;
	}

	mint operator-(const mint &other) const {
		int res = data + mod - other.data;
		if (res >= mod) {
			res -= mod;
		}
		return res;
	}

	mint operator*(const mint &other) const {
		return mint(1ll * data * other.data % mod);
	}
};

int n;
vector<int> X, Y;

constexpr int maxn = 1 << 19; 

namespace st0 {
	int tree[maxn * 2 - 1];

	void set(int i, int x = 0, int lx = 0, int rx = maxn) {
		if (rx - lx == 1) {
			tree[x] = i;
			return;
		}

		int mx = (lx + rx) / 2;

		if (i < mx) {
			set(i, x * 2 + 1, lx, mx);
		} else {
			set(i, x * 2 + 2, mx, rx);
		}

		if (Y[tree[x * 2 + 1]] > Y[tree[x * 2 + 2]]) {
			tree[x] = tree[x * 2 + 1];
		} else {
			tree[x] = tree[x * 2 + 2];
		}
	}

	int get(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
		int res = l;
		for (int i = l; i < r; i++) {
			if (Y[res] < Y[i]) {
				res = i;
			}
		}
		return res;
		if (l <= lx && rx <= r) {
			return tree[x];
		}

		if (l >= rx || lx >= r) {
			return n;
		}

		int mx = (lx + rx) / 2;

		int i = get(l, r, x * 2 + 1, lx, mx);
		int j = get(l, r, x * 2 + 2, mx, rx);

		if (Y[i] > Y[j]) {
			return i;
		} else {
			return j;
		}
	}
} // namespace st0

namespace st1 {
	int tree[maxn * 2 - 1];

	void set(int i, int v, int x = 0, int lx = 0, int rx = maxn) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}

		int mx = (lx + rx) / 2;

		if (i < mx) {
			set(i, v, x * 2 + 1, lx, mx);
		} else {
			set(i, v, x * 2 + 2, mx, rx);
		}

		tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
	}

	int get(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
		// int res = 0;
		// for (int i = l; i < r; i++) {
		// 	res = max(res, X[i]);
		// }
		// return res;
		if (l <= lx && rx <= r) {
			return tree[x];
		}

		if (l >= rx || lx >= r) {
			return 0;
		}
		
		return max(
			get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
			get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
		);
	}
} // namespace st1

namespace st2 {
	mint tree[maxn * 2 - 1];

	void set(int i, int v, int x = 0, int lx = 0, int rx = maxn) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}

		int mx = (lx + rx) / 2;
		
		if (i < mx) {
			set(i, v, x * 2 + 1, lx, mx);
		} else {
			set(i, v, x * 2 + 2, mx, rx);
		}

		tree[x] = tree[x * 2 + 1] * tree[x * 2 + 2];
	}

	mint get(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
		if (l <= lx && rx <= r) {
			return tree[x];
		}

		if (l >= rx || lx >= r) {
			return 1;
		}

		return get(l, r, x * 2 + 1, lx, (lx + rx) / 2) * get(l, r, x * 2 + 2, (lx + rx) / 2, rx);
	}
} // namespace st2

int calc() {
	vector<pair<int, int>> q;

	{
		i128 cur = 1;

		for (int r = n - 1; r >= 0;) {
			int R = r + 1;

			for (int j = 19; r >= 0 && j >= 0 && X[r] == 1; j--) {
				if (R - (1 << j) >= 0 && st1::get(R - (1 << j), R) == 1) {
					r -= (1 << j);
				}
			}

			if (r == -1) {
				r = 0;
			}

			cur *= X[r];

			if (cur > 1e18) {
				break;
			} else {
				q.emplace_back(r, st0::get(r, R));
			}

			r--;
		}
	}

	reverse(q.begin(), q.end());

	vector<pair<i128, int>> v;
	for (i128 cur = 1; auto [a, b] : q) {
		cur *= X[a];
		v.emplace_back(cur * Y[b], b);
	}

	int pos = max_element(v.begin(), v.end())->second;

	return (st2::get(0, pos + 1) * Y[pos]).data;
}

int init(int N, int _X[], int _Y[]) {
	n = N;
	
	X = vector<int>(_X, _X + n);
	Y = vector<int>(_Y, _Y + n);
	Y.push_back(0);

	for (int i = 0; i < n; i++) {
		st0::set(i);

		st1::set(i, X[i]);
		st2::set(i, X[i]);
	}

	return calc();
}

int updateX(int pos, int val) {	
	X[pos] = val;

	st1::set(pos, val);
	st2::set(pos, val);

	return calc();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	
	st0::set(pos);

	return calc();
}