#include "horses.h"
#include <cmath>
#include <vector>
#include <iostream>
using ll = long long;
using ld = long double;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 500000;
int const modulo = 1000000007;
void gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
} else {
gcd(b, a % b, x, y);
int aux = x;
x = y;
y = aux - a / b * y;
}
}
struct Number{
ld lg;
int val;
Number(int val = 1){
lg = log(val);
this->val = val % modulo;
}
Number operator * (Number const &a) const{
Number result;
result.lg = lg + a.lg;
result.val = 1LL * val * a.val % modulo;
return result;
}
Number operator / (Number const &a) const{
Number result;
result.lg = lg - a.lg;
int x, y;
gcd(a.val, modulo, x, y);
x = x % modulo;
if(x < 0)
x += modulo;
result.val = 1LL * val * x % modulo;
return result;
}
bool operator < (Number const &a) const{
return lg < a.lg;
}
};
class SegmentTree{
private:
std::vector<Number> aint;
std::vector<Number> lazy;
public:
SegmentTree(int n = 0){
aint.resize(4 * n);
lazy.resize(4 * n);
}
void cleannode(int node, int from, int to){
if(from < to){
int mid = (from + to) / 2;
lazy[node * 2] = lazy[node * 2] * lazy[node];
lazy[node * 2 + 1] = lazy[node * 2 + 1] * lazy[node];
}
aint[node] = aint[node] * lazy[node];
lazy[node] = 1;
}
void computenode(int node, int from, int to){
if(from < to){
int mid = (from + to) / 2;
if(aint[node * 2] < aint[node * 2 + 1])
aint[node] = aint[node * 2 + 1];
else
aint[node] = aint[node * 2];
}
}
void update(int node, int from, int to, int x, int y, Number val){
if(from == x && to == y){
lazy[node] = lazy[node] * val;
cleannode(node, from, to);
} else {
int mid = (from + to) / 2;
cleannode(node * 2, from, mid);
cleannode(node * 2 + 1, mid + 1, to);
if(x <= mid)
update(node * 2, from, mid, x, MIN(mid, y), val);
if(mid + 1 <= y)
update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
computenode(node, from, to);
}
}
Number query(int node, int from, int to, int x, int y){
cleannode(node, from, to);
if(from == x && to == y){
return aint[node];
} else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, x, y);
else{
Number result = query(node * 2, from, mid, x, mid);
Number result2 = query(node * 2 + 1, mid + 1, to, mid + 1, y);
if(result < result2)
return result2;
else
return result;
}
}
}
};
SegmentTree aint;
int n;
int X[1 + nmax];
int Y[1 + nmax];
int init(int N_, int X_[], int Y_[]) {
n = N_;
aint = SegmentTree(n);
for(int i = 0; i < n; i++)
X[i] = X_[i];
for(int i = 0; i < n; i++)
Y[i] = Y_[i];
for(int i = 0; i < n; i++)
aint.update(1, 0, n - 1, i, n - 1, X[i]);
for(int i = 0; i < n; i++)
aint.update(1, 0, n - 1, i, i, Y[i]);
return aint.query(1, 0, n - 1, 0, n - 1).val;
}
int updateX(int pos, int val) {
aint.update(1, 0, n - 1, pos, n - 1, Number(val) / Number(X[pos]));
X[pos] = val;
return aint.query(1, 0, n - 1, 0, n - 1).val;
}
int updateY(int pos, int val) {
aint.update(1, 0, n - 1, pos, pos, Number(val) / Number(Y[pos]));
Y[pos] = val;
return aint.query(1, 0, n - 1, 0, n - 1).val;
}
