#include "hexagon.h"
#include <iostream>
#include <vector>
#include <cmath>
#include<map>
#include <algorithm>
#include <iomanip>
#include <string>
#include<stack>
#include <set>
#include <queue>
#include <chrono>
#include<array>
#include<bitset>
#include<unordered_map>
#include<random>
#include<cassert>
#include<cstring>
using namespace std;
using ll = long long;
using db = double;
const float pi = 3.14159265359;
#define V vector
#define VI V<int>
#define P pair<int,int>
#define rep(i, a, b, step) for (int i = int(a); i <= int(b); i += step)
#define repl(i,a,b,step) for (int i = int(a); i >= int(b); i -= step)
#define prime(n) [](int x) { for (int i = 2; i *1ll* i <= x; ++i) if (x % i == 0) return false; return x > 1; }(n)
#define printall(container, ch) for (const auto& elem : container) { std::cout << elem << ch; } std::cout << std::endl;
#define sn << '\n'
#define ed << endl
#define sz size()
#define print cout <<
#define debug(x) cerr<< #x << " = " << x sn;
#define mpII map<int,int>
#define mine min_element
#define maxe max_element
#define all(v) begin(v), end(v)
#define txt freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout)
#define pb push_back
#define pq priority_queue
#define rev reverse
#define nuyn(a) a.erase(unique(all(a)), end(a))
#define nx next_permutation
#define pk pop_back()
#define START print "Start" sn
#define END print "End" sn
#define ff first
#define ss second
#define ts to_string
#define ub upper_bound
#define mk make_pair
#define lb lower_bound
#define testcase int t;cin>>t;while(t--)solution();
const int N = 2e3 + 3, mod = 1e9 + 7;
int dx[6] = { 0,1,1,0,-1,-1 }, dy[6] = { 2,1,-1,-2,-1,1 };
bool vis[2 * N + 1][2 * N + 1], close[2 * N + 1][2 * N + 1], pt[2 * N + 1][2 * N + 1];
int draw_territory(int n, int a, int b, std::vector<int> d, std::vector<int> l) {
int x = N - 2, y = N - 2, n_x, n_y, nc = N * 2, ds;
ll ans = 0;
vis[x][y] = 1;
queue<array<int, 3>>q;
queue<P>qc;
q.push({ x,y,0 });
pt[x][y] = 1;
rep(i, 0, n - 1, 1) {
--d[i];
while (l[i]--) {
x += dx[d[i]];
y += dy[d[i]];
pt[x][y] = 1;
}
}
qc.push({ 0,0 });
while (!qc.empty()) {
x = qc.front().ff;
y = qc.front().ss;
close[x][y] = 1;
qc.pop();
rep(i, 0, 5, 1) {
n_x = dx[i] + x;
n_y = dy[i] + y;
if (n_x<0 or n_x>nc or n_y<0 or n_y>nc or pt[n_x][n_y] or close[n_x][n_y])continue;
close[n_x][n_y] = 1;
qc.push({ n_x,n_y });
}
}
array<int, 3>cur;
while (!q.empty()) {
cur = q.front();
x = cur[0];
y = cur[1];
ds = cur[2];
q.pop();
ans += (a * 1ll + ds * 1ll * b) % mod;
ans %= mod;
rep(i, 0, 5, 1) {
n_x = dx[i] + x;
n_y = dy[i] + y;
if (n_x<0 or n_x>nc or n_y<0 or n_y>nc or vis[n_x][n_y] or close[n_x][n_y])continue;
vis[n_x][n_y] = 1;
q.push({ n_x,n_y,ds + 1 });
}
}
return ans;
}
