#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array
#define vct vector
#define hmap unordered_map
#define hset unordered_set
#define pll pair<lint, lint>
#define fir first
#define sec second
#define lb lower_bound
const lint MD = 1e9 + 7, N_NDS = 1e6 + 5, INF = 1e18, INV = 5e8 + 4;
lint n, a, b;
vct<lint> drc, lng;
lint md(lint x) { return (x + MD) % MD; }
pll mv(pll pt, lint drc, lint lng) {
pll dlt;
if (drc == 1) dlt = {0, 1};
if (drc == 2) dlt = {1, 1};
if (drc == 3) dlt = {1, 0};
if (drc == 4) dlt = {0, -1};
if (drc == 5) dlt = {-1, -1};
if (drc == 6) dlt = {-1, 0};
return {pt.fir + dlt.fir * lng, pt.sec + dlt.sec * lng};
}
vct<pll> gt_pts() {
pll pt = {0, 0};
vct<pll> ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < lng[i]; j++) {
pt = mv(pt, drc[i], 1);
ans.push_back(pt);
}
}
return ans;
}
vct<pll> nghbrs(pll pt) {
vct<pll> ans;
for (int i = 1; i <= 6; i++) ans.push_back(mv(pt, i, 1));
return ans;
}
set<pll> pt_nds, pth_nds, vs;
void dfs(pll pt) {
vs.insert(pt);
for (pll nw_pt : nghbrs(pt))
if (pt_nds.count(nw_pt) && !vs.count(nw_pt) && !pth_nds.count(nw_pt)) dfs(nw_pt);
}
hmap<lint, vct<pll>> clmns;
int n_nds;
arr<lint, N_NDS> x;
arr<pll, N_NDS> y;
lint prcmp1() {
vct<pll> pts = gt_pts();
for (pll pt : pts) {
pt_nds.insert(pt), pth_nds.insert(pt);
for (pll nw_pt : nghbrs(pt)) pt_nds.insert(nw_pt);
}
pll mn_x;
for (pll pt : pt_nds) mn_x = min(mn_x, pt);
dfs(mn_x);
for (pll pt : pts) clmns[pt.fir].push_back(pt);
for (pair<lint, vct<pll>> clmn : clmns) {
sort(clmn.sec.begin(), clmn.sec.end());
for (pll pt : clmn.sec) {
if (vs.count({pt.fir, pt.sec - 1})) n_nds++, x[n_nds] = clmn.fir, y[n_nds] = {pt.sec, 0};
if (vs.count({pt.fir, pt.sec + 1})) y[n_nds].sec = pt.sec;
}
}
// for (int u = 1; u <= n_nds; u++) {
// cout << u << ": " << x[u] << " " << y[u].fir << " " << y[u].sec << endl;
// }
lint ans = 0;
for (int u = 1; u <= n_nds; u++) ans += y[u].sec - y[u].fir + 1;
return ans;
}
hmap<lint, map<pll, int>> nd;
hmap<lint, set<pll>> ys;
arr<vct<int>, N_NDS> adj;
int rt;
arr<lint, N_NDS> lw;
arr<pll, N_NDS> rng;
arr<bool, N_NDS> sn;
void dfs2(int u) {
sn[u] = true;
for (int v : adj[u]) {
if (sn[v]) continue;
pll intr = {max(rng[u].fir, y[v].fir), min(rng[u].sec + 1, y[v].sec)};
if (intr.fir <= intr.sec) rng[v] = intr, lw[v] = lw[u] + 1;
else if (rng[u].sec < y[v].fir) rng[v] = {y[v].fir, y[v].fir}, lw[v] = lw[u] + y[v].fir - rng[u].sec + 1;
else {
assert(y[v].sec < rng[u].fir);
rng[v] = {y[v].sec, y[v].sec}, lw[v] = lw[u] + rng[u].fir - y[v].sec + 1;
}
dfs2(v);
}
}
void prcmp2() {
for (int u = 1; u <= n_nds; u++)
nd[x[u]][y[u]] = u, ys[x[u]].insert(y[u]);
for (int u = 1; u <= n_nds; u++) {
for (lint nw_x : {x[u] - 1, x[u] + 1}) {
auto it1 = ys[nw_x].lb({y[u].fir, -INF});
if (it1 != ys[nw_x].begin())
if (next(it1, -1)->sec >= y[u].fir)
adj[u].push_back(nd[nw_x][*next(it1, -1)]);
for (auto it2 = it1; it2 != ys[nw_x].end() && it2->fir <= y[u].sec; it2++)
adj[u].push_back(nd[nw_x][*it2]);
}
}
rt = nd[0][*next(ys[0].lb({1, -1}), -1)];
lw[rt] = 0, rng[rt] = {0, 0};
dfs2(rt);
// cout << y[rt].fir << " " << y[rt].sec << endl;
// for (int u = 1; u <= n_nds; u++) {
// cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": ";
// for (int v : adj[u]) cout << x[v] << "," << y[v].fir << "," << y[v].sec << " ";
// // for (int v : adj[u]) cout << v << " ";
// cout << endl;
// }
}
lint sm(lint x, lint y) {
if (x > y) return 0;
return md(md(md(x + y) * md(y - x + 1)) * INV);
}
int draw_territory(int _n, int _a, int _b, vct<int> _drc, vct<int> _lng) {
n = _n, a = _a, b = _b;
for (int i = 0; i < n; i++) drc.push_back(_drc[i]), lng.push_back(_lng[i]);
lint ar = prcmp1();
lint ans = md(ar * a);
prcmp2();
// for (int u = 1; u <= n_nds; u++) {
// cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": " << lw[u] << "," << rng[u].fir << "," << rng[u].sec << endl;
// }
for (int u = 1; u <= n_nds; u++) {
lint inc_ans = md(b * md(lw[u] * (rng[u].sec - rng[u].fir + 1) +
sm(lw[u] + 1, lw[u] + rng[u].fir - y[u].fir) +
sm(lw[u] + 1, lw[u] + y[u].sec - rng[u].sec)));
ans = md(ans + inc_ans);
}
return ans;
}
