#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const ll mod=1e9+7;
const int MAX_N=8e3;
int X[8]={0,-2,-1,1,2,1,-1};
int Y[8]={0,0,1,1,0,-1,-1};
ll he[MAX_N+10][MAX_N+10];
int vis[MAX_N+10][MAX_N+10];
ll pot(ll b,ll e){
if(e==1) return b;
ll aux=pot(b,e/2);
aux*=aux; aux%=mod;
if(e%2!=0) aux=(aux*b)%mod;
return aux;
}
void flod(int x,int y){
vis[x][y]=2;
queue<ii> q;
q.push(ii(x,y));
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=1;i<=6;i++){
int xk=x+X[i];
int yk=y+Y[i];
if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && !vis[xk][yk]){
vis[xk][yk]=2;
q.push(ii(xk,yk));
}
}
}
}
void height(int x,int y){
for(int i=0;i<=MAX_N;i++) for(int j=0;j<=MAX_N;j++) he[i][j]=1e9;
he[x][y]=0;
queue<ii> q;
q.push(ii(x,y));
while(!q.empty()){
int xi=q.front().first;
int yi=q.front().second;
q.pop();
for(int i=1;i<=6;i++){
int xk=xi+X[i];
int yk=yi+Y[i];
if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && vis[xk][yk]<=1){
if(he[xk][yk]>he[xi][yi]+1){
he[xk][yk]=he[xi][yi]+1;
q.push(ii(xk,yk));
}
}
}
}
}
int draw_territory(int N, int A, int B,
std::vector<int> D, std::vector<int> L) {
memset(he,-1,sizeof he);
memset(vis,0,sizeof vis);
ll ans=0;
int x=4e3,y=4e3;
vis[x][y]=1;
for(int i=0;i<N;i++){
for(int j=0;j<L[i];j++){
x+=X[D[i]];
y+=Y[D[i]];
vis[x][y]=1;
}
}
for(int i=1;i<=6;i++){
x=4e3; y=4e3;
while(x>=0 && y>=0 && x<=MAX_N && y<=MAX_N){
x+=X[i];
y+=Y[i];
}
x-=X[i];
y-=Y[i];
if(!vis[x][y]){
flod(x,y);
break;
}
}
x=4e3; y=4e3;
height(x,y);
for(int i=0;i<=MAX_N;i++){
for(int j=0;j<=MAX_N;j++){
if(he[i][j]!=1e9){
ans+=A; ans%=mod;
ans+=B*he[i][j]; ans%=mod;
}
}
}
return ans;
}
