#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define pii pair<int,int>
#define int long long
int mod = 1e9+7;
struct SegmentTree{
int len = 1;
vector<int> S;
SegmentTree(int n){
while(len < n) len <<= 1;
S.resize(2*len, 1);
}
int query(int ql, int qr, int l= 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return 1;
int mid = (l+r)/2;
return (query(ql,qr,l,mid,i*2) * query(ql,qr,mid,r,i*2+1)) % mod;
}
void upd(int i, int v){
i += len;
S[i] = v;
for(i /= 2; i > 0; i /= 2){
S[i] = (S[i*2] * S[i*2+1])% mod;
}
}
};
int32_t init(int32_t n, int32_t mult[], int32_t cost[]) {
vector<int> X(n);
vector<int> Y(n);
for(int i = 0; i < n; i++){
X[i] = mult[i];
Y[i] = cost[i];
}
SegmentTree seg(n);
for(int i = 0;i < n; i++){
seg.upd(i, X[i]);
}
stack<pii> S;
S.push({0, X[0]});
for(int i = 1; i < n; i++){
int ncnt = 0;
while(S.size()){
int ind, sz;
tie(ind,sz) = S.top();
int c = Y[ind];
int amt = seg.query(ind+1, i+1);
int nc = (amt) * Y[i];
if(c <= nc){
ncnt += (sz*amt);
S.pop();
}else{
break;
}
}
S.push({i,ncnt});
}
int r = 0;
while(S.size()){
r += Y[S.top().first] * S.top().second;
S.pop();
}
return r;
}
int32_t updateX(int32_t pos, int32_t val) {
return 0;
}
int32_t updateY(int32_t pos, int32_t val) {
return 0;
}
