#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 1e9;
const int mod = 1e9+7;
const int inv2 = (mod+1)/2;
int dx[]={0,0,1,1,0,-1,-1},
dy[]={0,1,1,0,-1,-1,0};
i32 draw_territory(i32 N, i32 A, i32 B,
std::vector<i32> D, std::vector<i32> L) {
int X=0,Y=0;
int a=0,b=0;
for(int i=0;i<N;i++){
b+=L[i];
int nX=X+L[i]*dx[D[i]];
int nY=Y+L[i]*dy[D[i]];
a+=X*nY-Y*nX;
X=nX;Y=nY;
}
a=(abs(a)+b)%mod;
a=a*inv2%mod;
a=(a+1)%mod;
X=0,Y=0;
vector<pii> p;
set<pii> ss;
for(int i=0;i<N;i++){
for(int j=0;j<L[i];j++){
X+=dx[D[i]];
Y+=dy[D[i]];
p.push_back({X,Y});
for(int t=1;t<=6;t++) ss.insert({X+dx[t],Y+dy[t]});
}
}
for(pii x:p) ss.erase(x);
set<pii> outers;
queue<pii> q;
q.push(*ss.begin());
outers.insert(*ss.begin());
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int t=1;t<=6;t++){
pii cc={x+dx[t],y+dy[t]};
if(ss.find(cc)!=ss.end() && outers.find(cc)==outers.end()){
q.push(cc);
outers.insert(cc);
}
}
}
map<int,vector<int>> mp;
for(pii x:p){
if(outers.find({x.fi,x.se-1})!=outers.end()) mp[x.fi].push_back(x.se);
if(outers.find({x.fi,x.se+1})!=outers.end()) mp[x.fi].push_back(x.se);
}
int rt=-1,M=0,T=0;
vector<int> cx;
vector<pii> range;
vector<vector<int>> edge;
int px=-inf;
vector<pii> pre;
for(auto [x,v]:mp){
sort(v.begin(),v.end());
vector<pii> cc;
for(int i=0;i<(int)v.size();i+=2){
cc.push_back({v[i],v[i+1]});
//cout << x << ' ' << v[i] << ' ' << v[i+1] << '\n';
}
if(px+1==x){
int pos=0,S=M-(int)pre.size();
for(auto p:cc){
int l=p.fi,r=p.se;
if(x==0 && l<=0 && 0<=r) rt=M;
cx.push_back(x);
edge.push_back({});
range.push_back({l,r});
while(pos<(int)pre.size() && pre[pos].se+1<l) pos++;
int lst=pos;
while(pos<(int)pre.size() && pre[pos].fi<=r){
edge[S+pos].push_back(M);
edge[M].push_back(S+pos);
lst=pos++;
}
pos=lst;M++;
}
}
else{
for(auto p:cc){
if(x==0 && p.fi<=0 && 0<=p.se) rt=M;
cx.push_back(x);
edge.push_back({});
range.push_back({p.fi,p.se});
M++;
}
}
px=x;pre=cc;
}
function<void(int,int,int,int,int)> dfs = [&](int u,int p,int l,int r,int d){
auto [L,R]=range[u];
//cout << u << ' ' << l << ' ' << r << ' ' << d << '\n';
T=(T+(R-L+1)*d+(l-L)*(l-L+1)/2+(R-r)*(R-r+1)/2)%mod;
for(int v:edge[u]){
if(v==p) continue;
auto [nL,nR]=range[v];
int nl=l-(cx[v]<cx[u]),nr=r+(cx[v]>cx[u]);
int cl=max(nl,nL),cr=min(nr,nR);
if(cl<=cr) dfs(v,u,cl,cr,d+1);
else if(nr<nL) dfs(v,u,nL,nL,d+nL-nr+1);
else dfs(v,u,nR,nR,d+nl-nR+1);
}
};
dfs(rt,-1,0,0,0);
return (a*A+T*B)%mod;
}
#undef int
