#include "hexagon.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int mod=1e9+7;
const int MAXN=4068;
int grid[MAXN][MAXN];
int binpow(int n,int k){
int curr=1;
for(;k;k>>=1){
if(k&1){
curr=(1LL*curr*n%mod);
}
n=(1LL*n*n%mod);
}
return curr;
}
int draw_territory(int n,int a,int b,vector<int> d,vector<int> l){
if(n==3){
int len=l[0]+1;
int cnt=(1LL*len*(len+1)/2)%mod;
int sum=(1LL*len*(len+1)%mod*(2*len+1)%mod*binpow(6,mod-2)%mod);
sum=(sum-cnt+mod)%mod;
int ans=(1LL*cnt*a%mod)+(1LL*sum*b%mod);
ans%=mod;
return ans;
}
if(b==0){
int x=0,y=0;
vector<pair<int,int>> v;
v.push_back({x,y});
long long in=0,bound=0,area=0;
for(int i=0;i<n;i++){
if(d[i]==1){
x+=l[i];
}
else if(d[i]==2){
y+=l[i];
}
else if(d[i]==3){
y+=l[i],x-=l[i];
}
else if(d[i]==4){
x-=l[i];
}
else if(d[i]==5){
y-=l[i];
}
else{
x+=l[i],y-=l[i];
}
v.push_back({x,y});
bound+=l[i],bound%=mod;
}
for(int i=0;i<n;i++){
int x1=v[i].first,y1=v[i].second,x2=v[(i+1)%n].first,y2=v[(i+1)%n].second;
area+=(1LL*x1*y2-1LL*y1*x2);
}
area=(1LL*abs(area)%mod*binpow(2,mod-2)%mod);
in=(area-(1LL*bound*binpow(2,mod-2)%mod)+1)%mod;
in=(in+mod)%mod;
return (1LL*(in+bound)*a%mod);
}
int tempo=0;
memset(grid,-1,sizeof(grid));
int x=MAXN/2,y=MAXN/2;
grid[x][y]=-2;
int sx=MAXN/2,sy=MAXN/2;
int Minx=0,Maxx=0,Miny=0,Maxy=0;
for(int i=0;i<n;i++){
tempo+=l[i];
for(int bruh=0;bruh<l[i];bruh++){
if(d[i]==1){
x++;
}
else if(d[i]==2){
y++;
}
else if(d[i]==3){
y++,x--;
}
else if(d[i]==4){
x--;
}
else if(d[i]==5){
y--;
}
else{
x++,y--;
}
Minx=min(Minx,x-sx);
Miny=min(Miny,y-sy);
Maxx=max(Maxx,x-sx);
Maxy=max(Maxy,y-sy);
grid[x][y]=-2;
}
}
// cout << Minx << ' ' << Miny << ' ' << Maxx << ' ' << Maxy << endl;
// for(int i=0;i<MAXN;i++){
// for(int j=0;j<MAXN;j++){
// if(grid[i][j]==-2){
// cout << '#';
// }
// else if(grid[i][j]==-3){
// cout << '0';
// }
// else{
// cout << '.';
// }
// }
// cout << endl;
// }
assert(grid[0][0]==-1);
int dx[]={1,-1,0,0,1,-1};
int dy[]={0,0,1,-1,-1,1};
int dir=6;
queue<pair<int,int>> q;
q.push({0,0});
grid[0][0]=-3;
while(!q.empty()){
x=q.front().first,y=q.front().second;
q.pop();
for(int k=0;k<dir;k++){
x+=dx[k],y+=dy[k];
if(x>=0&&x<MAXN&&y>=0&&y<MAXN&&grid[x][y]==-1){
grid[x][y]=-3;
q.push({x,y});
}
x-=dx[k],y-=dy[k];
}
}
// cout << "PHASE 2: " << endl;
// for(int i=0;i<MAXN;i++){
// for(int j=0;j<MAXN;j++){
// if(grid[i][j]==-2){
// cout << '#';
// }
// else if(grid[i][j]==-3){
// cout << '0';
// }
// else{
// cout << '.';
// }
// }
// cout << endl;
// }
q.push({MAXN/2,MAXN/2});
grid[MAXN/2][MAXN/2]=0;
int ans=0;
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
ans+=a,ans%=mod;
ans+=(1LL*grid[x][y]*b%mod);
ans%=mod;
int dist=grid[x][y];
for(int k=0;k<dir;k++){
x+=dx[k],y+=dy[k];
if(x>=0&&x<MAXN&&y>=0&&y<MAXN&&(grid[x][y]==-1||grid[x][y]==-2)){
grid[x][y]=dist+1;
q.push({x,y});
}
x-=dx[k],y-=dy[k];
}
}
return ans;
}
