#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const long long MOD=1e9+7,INC=2000;
int X[]={0,0,1,1,0,-1,-1};
int Y[]={0,1,1,0,-1,-1,0};
int DD[4005][4005];
bool block[4005][4005],mark[4005][4005];
void move(int &curX,int &curY,int d) {
if(d==1)
curY++;
else if(d==2)
curX++,curY++;
else if(d==3)
curX++;
else if(d==4)
curY--;
else if(d==5)
curX--,curY--;
else
curX--;
}
long long mult(long long x,long long k) {
if(k==0)
return 1;
long long tmp=mult(x,k/2);
if(k%2==0)
return tmp*tmp%MOD;
return tmp*tmp%MOD*x%MOD;
}
void dfs(int u,int v) {
mark[u][v]=true;
for(int d=1;d<=6;d++) {
int newU=u,newV=v;
move(newU,newV,d);
if(newU<0||newU>2*INC||newV<0||newV>2*INC||block[newU][newV]||mark[newU][newV])
continue;
dfs(newU,newV);
}
}
int draw_territory(int N, int A, int B,
std::vector<int> D, std::vector<int> L) {
if(N==3) {
long long l=L[0];
long long cnt=(l+1)*(l+2)%MOD*mult(2,MOD-2)%MOD;
long long dist=(l*(l+1)%MOD*mult(2,MOD-2)%MOD
+l*(l+1)%MOD*(2*l+1)%MOD*mult(6,MOD-2)%MOD)%MOD;
return (cnt*A+dist*B)%MOD;
} else if(accumulate(L.begin(),L.end(),0)<=2000) {
int curX=0,curY=0;
block[curX+INC][curY+INC]=true;
for(int i=0;i<N;i++)
while(L[i]--) {
move(curX,curY,D[i]);
block[curX+INC][curY+INC]=true;
}
dfs(0,0);
for(int i=0;i<=2*INC;i++)
for(int j=0;j<=2*INC;j++)
DD[i][j]=-1;
DD[INC][INC]=0;
queue<ii> Q;
Q.push({INC,INC});
while(!Q.empty()) {
int u=Q.front().first,v=Q.front().second;
Q.pop();
for(int d=1;d<=6;d++) {
int newU=u,newV=v;
move(newU,newV,d);
if(newU<0||newU>2*INC||newV<0||newV>2*INC||DD[newU][newV]!=-1||mark[newU][newV])
continue;
DD[newU][newV]=DD[u][v]+1;
Q.push({newU,newV});
}
}
long long cnt=0,dist=0;
for(int i=0;i<=2*INC;i++)
for(int j=0;j<=2*INC;j++)
if(!mark[i][j]) {
cnt++;
dist=(dist+DD[i][j])%MOD;
}
return (cnt*A+dist*B)%MOD;
} else if(B==0) {
// Pick's theorem
long long boundary=accumulate(L.begin(),L.end(),0);
vector<ii> segs;
segs.push_back({0,0});
for(int i=0;i<N;i++) {
int newX=segs.back().first+X[D[i]]*L[i];
int newY=segs.back().second+Y[D[i]]*L[i];
segs.push_back({newX,newY});
}
long long area=0;
for(int i=1;i<segs.size();i++)
area+=1LL*segs[i].first*segs[i-1].second-1LL*segs[i].second*segs[i-1].first;
area=abs(area);
long long inside=((area-boundary)/2+1)%MOD;
return (boundary+inside)*A%MOD;
}
return 0;
}
