#include "hexagon.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define MAX_N 1200
#define MOD 1000000007
lli mat[2][MAX_N][MAX_N], frontera[2][MAX_N][MAX_N], llenado[2][MAX_N][MAX_N];
lli pmat, pfil, pcol;
bool sigpos(lli &matriz, lli &fila, lli &columna, lli dir){
if (dir == 1){
if (!fila) return false;
--fila;
}
else if (dir == 2){
if (!matriz && !fila) return false;
if (!matriz) --fila;
else ++columna;
matriz ^= 1;
}
else if (dir == 3){
if (matriz && (fila == MAX_N - 1 || columna == MAX_N - 1)) return false;
if (matriz){ ++fila; ++columna; }
matriz ^= 1;
}
else if (dir == 4){
if (fila == MAX_N - 1) return false;
++fila;
}
else if (dir == 5){
if ((!matriz && !columna) || (matriz && fila == MAX_N - 1)) return false;
if (!matriz) --columna;
else ++fila;
matriz ^= 1;
}
else if (dir == 6){
if (!matriz && (!fila || !columna)) return false;
if (!matriz){ --fila; --columna; }
matriz ^= 1;
}
return true;
}
bool llena(lli m, lli f, lli c){
lli sm, sf, sc, cm, cf, cc;
queue<lli> qm, qf, qc;
bool res = false;
qm.push(m);
qf.push(f);
qc.push(c);
llenado[m][f][c] = 1;
while (!qm.empty()){
cm = qm.front(); qm.pop();
cf = qf.front(); qf.pop();
cc = qc.front(); qc.pop();
rep(dir, 1, 6){
sm = cm; sf = cf; sc = cc;
if (!sigpos(sm, sf, sc, dir)) { res = true; continue; }
if (!llenado[sm][sf][sc] && !frontera[sm][sf][sc]){
llenado[sm][sf][sc] = 1;
qm.push(sm);
qf.push(sf);
qc.push(sc);
}
}
}
return res;
}
int draw_territory(int N, int A, int B,
std::vector<int> D, std::vector<int> L) {
pmat = 0; pfil = MAX_N >> 1; pcol = MAX_N >> 1;
frontera[pmat][pfil][pcol] = 1;
rep(i, 0, N - 1){
rep(j, 1, L[i]){
sigpos(pmat, pfil, pcol, D[i]);
frontera[pmat][pfil][pcol] = 1;
}
}
// ENCUENTRA EL EXTERIOR;
rep(dir, 1, 6){
pmat = 0; pfil = MAX_N >> 1; pcol = MAX_N >> 1;
sigpos(pmat, pfil, pcol, dir);
if (!frontera[pmat][pfil][pcol]){
// HAZ EL FILL
if (llena(pmat, pfil, pcol)) break;
// LIMPIA EL LLENADO
rep(m, 0, 1) rep(f, 0, MAX_N - 1) rep(c, 0, MAX_N - 1) llenado[m][f][c] = 0;
}
}
lli sm, sf, sc, cm, cf, cc, res, dis;
queue<lli> qm, qf, qc, qd;
res = 0;
qm.push(0);
qf.push(MAX_N >> 1);
qc.push(MAX_N >> 1);
qd.push(0);
mat[0][MAX_N >> 1][MAX_N >> 1] = 1;
while (!qm.empty()){
cm = qm.front(); qm.pop();
cf = qf.front(); qf.pop();
cc = qc.front(); qc.pop();
dis = qd.front(); qd.pop();
res += A + ((B * dis) % MOD);
res %= MOD;
rep(dir, 1, 6){
sm = cm; sf = cf; sc = cc;
sigpos(sm, sf, sc, dir);
// SI NO ES PARTE EXTERNA O ES FRONTERA Y NO ESTA VISITADA, CUENTALO
if (!mat[sm][sf][sc] && (!llenado[sm][sf][sc] || frontera[sm][sf][sc])){
mat[sm][sf][sc] = 1; // VISITALA
qm.push(sm);
qf.push(sf);
qc.push(sc);
qd.push(dis + 1);
}
}
}
return res;
}
