#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define lso(x) x&(-x)
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
vi X, Y, T;
int n, N;
ll get() {
int start = n - 1;
ll pr = X[start];
while (pr < 2*1e9) {
start--;
if (start == 0) break;
pr *= X[start];
}
T.assign(n, 1);
rep(i, start, n) {
if (i == 0) T[i] = X[i];
else T[i] = T[i - 1] * X[i];
}
ll best = 0;
rep(i, start, n) {
best = max(best, T[i] * Y[i]);
}
best = best % 1000000009;
ll mult_prev = 1;
rep(i, 0, start) mult_prev = (mult_prev * X[i]) % 1000000009;
best = (best * mult_prev) % 1000000009;
return best;
}
int init(int a, int x[], int y[]) {
n = N = a;
X.resize(N); Y.resize(N); T.resize(N);
rep(i,0,N) X[i] = x[i];
rep(i,0,N) Y[i] = y[i];
return get();
}
int updateX(int pos, int val) {
X[pos] = val;
return get();
}
int updateY(int pos, int val) {
Y[pos] = val;
return get();
}
// int main() {
// int x[] = {1, 1, 1, 1, 2};
// int y[] = {1, 2, 3, 4, 5};
// cout << init(5, x, y);
// }
