#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
long long dx[] = {-1,0,1,1,0,-1}, dy[] = {1,1,0,-1,-1,0}, m = 1000000007, dist[2005][2005], ufds[4500005], rnk[4500005];
bitset<2005> bs[2005];
queue< pair<long long,long long> > q;
long long findSet(long long i) {
return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}
void unionSet(long long i, long long j) {
long long a = findSet(i), b = findSet(j);
if (a == b) return;
if (rnk[a] < rnk[b]) ufds[a] = b;
if (rnk[a] > rnk[b]) ufds[b] = a;
if (rnk[a] == rnk[b]) ufds[a] = b, rnk[b]++;
}
int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
for (long long i = 0; i <= 4500000; ++i) ufds[i] = i, rnk[i] = 1;
long long x = 1000, y = 1000;
for (long long i = 0; i < N; ++i) {
D[i]--;
for (long long j = 0; j < L[i]; ++j) x += dx[D[i]], y += dy[D[i]], bs[x][y] = 1;
}
for (long long i = 0; i <= 2000; ++i) for (long long j = 0; j <= 2000; ++j) for (long long k = 0; k < 6; ++k) {
long long x = i + dx[k], y = j + dy[k];
if (x >= 0 && x <= 2000 && y >= 0 && y <= 2000 && bs[i][j] == bs[x][y]) unionSet(i*2001+j,x*2001+y);
}
memset(dist,-1,sizeof(dist));
dist[1000][1000] = 0;
q.emplace(1000,1000);
long long ans = A;
while (!q.empty()) {
long long x,y; tie(x,y) = q.front(); q.pop();
for (long long k = 0; k < 6; ++k) {
long long nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx <= 2000 && ny >= 0 && ny <= 2000 && dist[nx][ny] == -1 && findSet(nx*2001+ny) != findSet(0)) {
dist[nx][ny] = dist[x][y] + 1;
q.emplace(nx,ny);
ans = (ans + A + dist[nx][ny] * B) % m;
}
}
}
return ans;
}
