#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "hexagon.h"
const ll MOD = 1e9 + 7;
ll nr(ll x) {
x %= MOD;
x += MOD;
x %= MOD;
return x;
}
int dirX[6] = {0, 1, 1, 0, -1, -1};
int dirY[6] = {-1, 0, 1, 1, 0, -1};
int N;
ll A, B;
vi D, L;
const int MAX = 4010;
vector<vector<bool>> grid(MAX, vector<bool>(MAX, false));
// true if filled
int draw_territory(int N_g, int A_g, int B_g, vector<int> D_g, vector<int> L_g) {
N = N_g; A = A_g; B = B_g;
for (int x : D_g)
D.pb(x - 1);
for (int x : L_g)
L.pb(x);
ii curr = {2005, 2005};
for (int i = 0; i < N; i++) {
grid[curr.fi][curr.se] = true;
for (int j = 0; j < L[i]; j++) {
curr.fi += dirX[D[i]];
curr.se += dirY[D[i]];
grid[curr.fi][curr.se] = true;
}
}
/* cout<<"grid: "<<endl;
for (int i = 1990; i <= 2020; i++) {
for (int j = 1990; j <= 2020; j++) {
if (i == 2005 && j == 2005)
cout<<"!";
else
cout<<grid[i][j];
}
cout<<endl;
}*/
queue<ii> q;
vector<vector<bool>> out(MAX, vector<bool>(MAX, false));
q.push({0, 0});
out[0][0] = true;
while (!q.empty()) {
int xc = q.front().fi;
int yc = q.front().se;
q.pop();
for (int i = 0; i < 6; i++) {
int xn = xc + dirX[i];
int yn = yc + dirY[i];
if (xn < 0 || xn >= MAX || yn < 0 || yn >= MAX)
continue;
if (!out[xn][yn] && !grid[xn][yn]) {
q.push({xn, yn});
out[xn][yn] = true;
}
}
}
/* cout<<"out: "<<endl;
for (int i = 1990; i <= 2020; i++) {
for (int j = 1990; j <= 2020; j++) {
if (i == 2005 && j == 2005)
cout<<"!";
else
cout<<out[i][j];
}
cout<<endl;
}*/
// q is empty
vector<vi> dist(MAX, vi(MAX, 1e9));
q.push({2005, 2005});
dist[2005][2005] = 0;
while (!q.empty()) {
int xc = q.front().fi;
int yc = q.front().se;
q.pop();
for (int i = 0; i < 6; i++) {
int xn = xc + dirX[i];
int yn = yc + dirY[i];
if (xn < 0 || xn >= MAX || yn < 0 || yn >= MAX)
continue;
if (!out[xn][yn] && dist[xn][yn] == 1e9) {
q.push({xn, yn});
dist[xn][yn] = dist[xc][yc] + 1;
}
}
}
/* cout<<"dist: "<<endl;
for (int i = 1990; i <= 2020; i++) {
for (int j = 1990; j <= 2020; j++) {
if (i == 2005 && j == 2005)
cout<<"! ";
else if (dist[i][j] == 1e9)
cout<<"- ";
else
cout<<dist[i][j]<<" ";
}
cout<<endl;
}*/
ll total = 0;
ll cnt = 0;
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
if (dist[i][j] != 1e9) {
total += dist[i][j];
total = nr(total);
cnt++;
}
}
}
ll ans = nr(cnt * A + total * B);
return ans;
}
