#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long pw(long long x, long long n) {
long long res = 1;
while (n > 0) {
if (n & 1) {
res = res * x % mod;
}
n /= 2;
x = x * x % mod;
}
return res;
}
const int N = 400400;
const int Q = 200200;
int dx[6] = {-1, -1, 0, 1, 1, 0};
int dy[6] = {-1, 0, 1, 1, 0, -1};
long long X = 0, Y = 0;
vector<int> v[N];
vector<pair<int, int>> g[N];
int G;
int A[N];
int B[N];
int a[N];
int b[N];
int f[N];
long long F(long long x) {
return x * (x + 1) / 2 % mod;
}
void dfs(int x, int p) {
Y += 1ll * f[x] * (B[x] - A[x] + 1) % mod;
Y += F(B[x] - b[x]) + F(a[x] - A[x]);
for (auto yy: g[x]) {
int y = yy.first;
int dir = yy.second;
if (y == p) {
continue;
}
a[y] = a[x] - 1;
b[y] = b[x] + 1;
f[y] = f[x] + 1;
if (dir == 1) {
a[y] += 1;
} else {
b[y] -= 1;
}
if (max(A[y], a[y]) > min(B[y], b[y])) {
if (b[y] < A[y]) {
f[y] += A[y] - b[y];
a[y] = b[y] = A[y];
} else {
f[y] += a[y] - B[y];
a[y] = b[y] = B[y];
}
} else {
a[y] = max(a[y], A[y]);
b[y] = min(b[y], B[y]);
}
dfs(y, x);
}
}
void work() {
for (int i = 0; i < N; i++) {
sort(v[i].begin(), v[i].end());
}
vector<int> shit;
int root = -1;
for (int i = 0; i < N; i++) {
assert (v[i].size() % 2 == 0);
vector<int> cur;
for (int j = 0; j < v[i].size(); j += 2) {
int l = v[i][j];
int r = v[i][j + 1];
G += 1;
A[G] = l;
B[G] = r;
X += r - l + 1;
cur.push_back(G);
if (A[G] <= 0 && 0 <= B[G] && i == Q) {
root = G;
}
}
for (int j = 0, h = 0; j < cur.size(); j++) {
while (h < shit.size() && B[shit[h]] < A[cur[j]]) {
h += 1;
}
if (h < shit.size() && A[shit[h]] <= B[cur[j]]) {
g[shit[h]].push_back({cur[j], 1});
g[cur[j]].push_back({shit[h], 0});
while (h + 1 < shit.size() && A[shit[h + 1]] <= B[cur[j]]) {
h += 1;
g[shit[h]].push_back({cur[j], 1});
g[cur[j]].push_back({shit[h], 0});
}
}
/*
for (int h = 0; h < shit.size(); h++) {
if (max(A[shit[h]], A[cur[j]]) <= min(B[shit[h]], B[cur[j]])) {
g[shit[h]].push_back({cur[j], 1});
g[cur[j]].push_back({shit[h], 0});
}
}
*/
}
swap(cur, shit);
}
dfs(root, root);
}
int draw_territory(int N, int A, int B,
std::vector<int> D, std::vector<int> L) {
if (N == 3) {
assert (L[0] == L[1]);
assert (L[1] == L[2]);
long long x = L[0] + 1;
X = x * (x + 1) / 2;
Y = x * (x + 1) % mod * (2 * x + 1) % mod * pw(6, mod - 2) - X;
} else {
vector<pair<int, int>> p;
set<pair<int, int>> fucked;
int x = 0, y = 0;
for (int i = 0; i < N; i++) {
int dir = D[i] - 1;
for (int j = 0; j < L[i]; j++) {
x += dx[dir];
y += dy[dir];
p.push_back({x, y});
for (int h = 0; h < 6; h++) {
fucked.insert({x + dx[h], y + dy[h]});
}
}
}
for (auto xi: p) {
fucked.erase(xi);
}
set<pair<int, int>> outers;
queue<pair<int, int>> q;
q.push(*fucked.begin());
outers.insert(*fucked.begin());
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 6; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (fucked.find({nx, ny}) == fucked.end()) {
continue;
} else if (outers.find({nx, ny}) == outers.end()) {
outers.insert({nx, ny});
q.push({nx, ny});
}
}
}
for (auto xi: p) {
int x = xi.first;
int y = xi.second;
if (outers.find({x, y - 1}) != outers.end()) {
v[x + Q].push_back(y);
}
if (outers.find({x, y + 1}) != outers.end()) {
v[x + Q].push_back(y);
}
}
work();
}
X %= mod;
Y %= mod;
long long res = X * A % mod + Y * B % mod;
res = (res % mod + mod) % mod;
return res;
}
