#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
struct segtree {
#define lc 2*v
#define rc 2*v+1
#define tm (tl+tr)/2
struct node {
long double logsum = 0;
long double logprof = 0;
ll product = 1;
ll profit = 0;
};
vector<node> tree;
vector<int> x, y;
void init(int n, vector<int> &X, vector<int> &Y) {
tree.resize(4*n);
x = X;
y = Y;
build(1, 1, n);
}
void pushup(int v) {
tree[v].logsum = tree[lc].logsum+tree[rc].logsum;
tree[v].product = (tree[lc].product*tree[rc].product) % MOD;
long double a = tree[lc].logsum+tree[rc].logprof;
long double b = tree[lc].logprof;
if (a > b) {
tree[v].logprof = a;
tree[v].profit = (tree[lc].product*tree[rc].profit) % MOD;
}
else {
tree[v].logprof = b;
tree[v].profit = tree[lc].profit;
}
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v].logsum = log2((long double)x[tl]);
tree[v].logprof = tree[v].logsum+log2((long double)y[tl]);
tree[v].product = x[tl];
tree[v].profit = (1ll*x[tl]*y[tl]) % MOD;
return;
}
build(lc, tl, tm);
build(rc, tm+1, tr);
pushup(v);
}
void update(int v, int tl, int tr, int pos) {
if (pos < tl || pos > tr) return;
if (tl == tr) {
tree[v].logsum = log2((long double)x[tl]);
tree[v].logprof = tree[v].logsum+log2((long double)y[tl]);
tree[v].product = x[tl];
tree[v].profit = (1ll*x[tl]*y[tl]) % MOD;
return;
}
update(lc, tl, tm, pos);
update(rc, tm+1, tr, pos);
pushup(v);
}
int query() {
return int((tree[1].profit) % MOD);
}
};
int n;
segtree stree;
int init(int N, int X[], int Y[]) {
vector<int> x(N+1), y(N+1);
for (int i = 0; i < N; i++) {
x[i+1] = X[i];
y[i+1] = Y[i];
}
n = N;
stree.init(n, x, y);
return stree.query();
}
int updateX(int pos, int val) {
stree.x[pos+1] = val;
stree.update(1, 1, n, pos+1);
return stree.query();
}
int updateY(int pos, int val) {
stree.y[pos+1] = val;
stree.update(1, 1, n, pos+1);
return stree.query();
}
