#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct drvo{
ld val;
ld lazy;
int prod;
int lazyprod;
} seg[4000000];
ld x[1000005];
ld y[1000005];
ld xpref[1000005];
int u1[1000005];
int xprod[1000005];
int x1[1000005];
int n;
const int MOD = 1000000007;
int mul(int a, int b){
return (1LL*a*b)%MOD;
}
ll pw(ll a, ll b){
if(b == 0) return 1;
ll res = pw(a, b/2);
res = (res*res)%MOD;
if(b%2) res = (res*a)%MOD;
return res;
}
void seginit(int node, int l, int r){
seg[node].lazyprod = 1;
if(l == r){
seg[node].val = xpref[l] + y[l];
seg[node].prod = mul(xprod[l], u1[l]);
return;
}
int mid = (l+r)/2;
seginit(node*2, l, mid);
seginit(node*2+1, mid+1, r);
if(seg[node*2].val > seg[node*2+1].val){
seg[node].val = seg[node*2].val;
seg[node].prod = seg[node*2].prod;
}
else{
seg[node].val = seg[node*2+1].val;
seg[node].prod = seg[node*2+1].prod;
}
}
void propagate(int node, int l, int r){
seg[node].val += seg[node].lazy;
seg[node].prod = mul(seg[node].prod, seg[node].lazyprod);
if(l == r){
seg[node].lazy = 0;
seg[node].lazyprod = 1;
return;
}
seg[node*2].lazy += seg[node].lazy;
seg[node*2].lazyprod = mul(seg[node*2].lazyprod, seg[node].lazyprod);
seg[node*2+1].lazy += seg[node].lazy;
seg[node*2+1].lazyprod = mul(seg[node*2+1].lazyprod, seg[node].lazyprod);
seg[node].lazy = 0;
seg[node].lazyprod = 1;
}
void upd(int node, int l, int r, int tl, int tr, ld val, int prod){
propagate(node, l, r);
if(l > tr || tl > r) return;
if(tl <= l && r <= tr){
seg[node].lazy += val;
seg[node].lazyprod = mul(seg[node].lazyprod, prod);
propagate(node, l, r);
return;
}
int mid = (l+r)/2;
upd(node*2, l, mid, tl, tr, val, prod);
upd(node*2+1, mid+1, r, tl, tr, val, prod);
if(seg[node*2].val > seg[node*2+1].val){
seg[node].val = seg[node*2].val;
seg[node].prod = seg[node*2].prod;
}
else{
seg[node].val = seg[node*2+1].val;
seg[node].prod = seg[node*2+1].prod;
}
}
int init(int N, int X[], int Y[]) {
n = N;
xprod[0] = 1;
for(int i=0; i<N; i++){
x[i+1] = log10l(X[i]);
x1[i+1] = X[i];
xpref[i+1] = x[i+1] + xpref[i];
xprod[i+1] = mul(xprod[i], X[i]);
y[i+1] = log10l(Y[i]);
u1[i+1] = Y[i];
}
seginit(1, 1, n);
return seg[1].prod;
}
int updateX(int pos, int val){
pos++;
ld g = x[pos];
x[pos] = log10l(val);
int f = x1[pos];
x1[pos] = val;
upd(1, 1, n, pos, n, x[pos]-g, mul(x1[pos], pw(f, MOD-2)));
return seg[1].prod;
}
int updateY(int pos, int val) {
pos++;
ld g = y[pos];
y[pos] = log10l(val);
int f = u1[pos];
u1[pos] = val;
upd(1, 1, n, pos, pos, y[pos]-g, mul(u1[pos], pw(f, MOD-2)));
return seg[1].prod;
}
