#include "hexagon.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 300005;
const int dx[6] = {0, 1, 1, 0, -1, -1};
const int dy[6] = {1, 1, 0, -1, -1, 0};
const int mod = 1e9 + 7;
struct mint {
int val;
mint() { val = 0; }
mint(const lint& v) {
val = (-mod <= v && v < mod) ? v : v % mod;
if (val < 0) val += mod;
}
friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
friend bool operator==(const mint& a, const mint& b) { return a.val == b.val; }
friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }
mint operator-() const { return mint(-val); }
mint& operator+=(const mint& m) { if ((val += m.val) >= mod) val -= mod; return *this; }
mint& operator-=(const mint& m) { if ((val -= m.val) < 0) val += mod; return *this; }
mint& operator*=(const mint& m) { val = (lint)val*m.val%mod; return *this; }
friend mint ipow(mint a, lint p) {
mint ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend mint inv(const mint& a) { assert(a.val); return ipow(a, mod - 2); }
mint& operator/=(const mint& m) { return (*this) *= inv(m); }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
operator int64_t() const {return val; }
};
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
bool turn(vector<pi> &a){
lint A = 0;
for(int i = 2; i < sz(a); i++) A += ccw(a[0], a[i-1], a[i]);
return A > 0;
}
struct node{
int p, s, e;
bool operator<(const node &n)const{
return pi(p, s) < pi(n.p, n.s);
}
};
vector<int> len[200005];
vector<node> vect;
vector<int> gph[MAXN];
mint solve(int x, int p, int d){
mint ret = mint(d) * mint(vect[x].e - vect[x].s + 1);
for(auto &i : gph[x]){
if(i != p) ret += solve(i, x, d + 1);
}
return ret;
}
int solve(vector<pi> v){
vect.clear();
for(int i = 0; i < MAXN; i++){
gph[i].clear();
}
int xmin = 1e9;
if(!turn(v)) reverse(v.begin() + 1, v.end());
for(auto &[x, y] : v){
xmin = min(xmin, x);
}
int xmax = 0;
for(auto &[x, y] : v){
x -= xmin;
xmax = max(xmax, x);
}
for(int i = 0; i < sz(v); i++){
auto s = v[i], e = v[(i + 1) % sz(v)];
auto p = v[(i + sz(v) - 1) % sz(v)];
if(s.first == e.first){
if(s.second < e.second){
if(p.first < s.first) len[s.first].push_back(s.second);
}
else{
if(p.first > s.first) len[s.first].push_back(s.second);
}
continue;
}
int delta = (e.second - s.second) / (e.first - s.first);
if(s.first < e.first){
if(p.first < s.first || (p.first == s.first && p.second > s.second)) len[s.first].push_back(s.second);
if(p.first > s.first){
len[s.first].push_back(s.second);
len[s.first].push_back(s.second);
}
for(int j = s.first + 1; j < e.first; j++) len[j].push_back(s.second + delta * (j - s.first));
}
else if(s.first > e.first){
if(p.first > s.first || (p.first == s.first && p.second < s.second)) len[s.first].push_back(s.second);
if(p.first < s.first){
len[s.first].push_back(s.second);
len[s.first].push_back(s.second);
}
for(int j = s.first - 1; j > e.first; j--) len[j].push_back(s.second + delta * (j - s.first));
}
}
for(int i = 0; i <= xmax; i++){
assert(sz(len[i]) % 2 == 0);
sort(all(len[i]));
vector<int> nlen = {len[i][0]};
for(int j = 1; j < sz(len[i]) / 2; j++){
if(len[i][2*j-1] + 1 == len[i][2*j]) continue;
nlen.push_back(len[i][2*j-1]);
nlen.push_back(len[i][2*j]);
}
nlen.push_back(len[i].back());
len[i].clear();
for(int j = 0; j < sz(nlen) / 2; j++){
vect.push_back({i, nlen[2*j], nlen[2*j+1]});
}
}
auto insec = [&](int j, int k){
return max(vect[j].s, vect[k].s) <= min(vect[j].e + 1, vect[k].e);
};
for(int i = 0; i < xmax; i++){
int p = lower_bound(all(vect), (node){i, -int(1e9), -1}) - vect.begin();
int q = lower_bound(all(vect), (node){i+1, -int(1e9), -1}) - vect.begin();
int r = lower_bound(all(vect), (node){i+2, -int(1e9), -1}) - vect.begin();
int k = q;
for(int j = p; j < q; j++){
while(k < r && vect[k].e < vect[j].s) k++;
if(insec(j, k)){
while(k < r && insec(j, k)){
gph[j].push_back(k);
gph[k].push_back(j);
k++;
}
k--;
}
}
}
// cout << "sz(vect) = " << sz(vect) << endl;
for(int i = 0; i < sz(vect); i++){
// printf("vect[%d] =(%d %d %d)\n", i, vect[i].p, vect[i].s, vect[i].e);
}
mint ans = 0;
for(int i = 0; i < sz(vect); i++){
if(vect[i].p == -xmin && vect[i].s <= 0 && 0 <= vect[i].e){
// cout << "init " << i << endl;
return solve(i, -1, 0);
}
}
assert(0);
}
int draw_territory(int N, int _A, int _B,
std::vector<int> D, std::vector<int> L) {
for(auto &i : D) i--;
vector<pi> a(N);
for(int i = 1; i < N; i++){
a[i].first = a[i-1].first + dx[D[i-1]] * L[i-1];
a[i].second = a[i-1].second + dy[D[i-1]] * L[i-1];
}
lint A = 0;
lint B = accumulate(all(L), 0ll);
for(int i = 2; i < N; i++) A += ccw(a[0], a[i-1], a[i]);
A = abs(A);
lint I = (A - B + 2) / 2;
mint sumA = mint(I + B) * mint(_A);
mint sumB = 0;
for(int _ = 0; _ < 3; _++){
if(_B == 0) continue;
vector<pi> a(N);
for(int i = 1; i < N; i++){
a[i].first = a[i-1].first + dx[D[i-1]] * L[i-1];
a[i].second = a[i-1].second + dy[D[i-1]] * L[i-1];
}
sumB += solve(a);
for(auto &j : D) j = (j + 1) % 6;
}
return sumA + mint(_B) * sumB / mint(2);
}
