// #pragma GCC target("avx2") #pragma GCC optimize("Ofast,unroll-loops") #include using namespace std; using ll = long long int; const ll MOD = 1000000007; ll N; vector S(200000),C(200000),seen(200000,0),siz(200000,0),par(200000,-1),root(200000,-1),id(200000,-1),dep(200000,0); vector> GG(200000),G(200000); void dfs1(ll x){ seen[x] = 1; siz[x] = 1; for(ll i = 0;i < (ll)GG[x].size();i++){ ll y = GG[x][i]; if(seen[y] == 1) continue; dep[y] = dep[x] + 1; G[x].emplace_back(y); dfs1(y); siz[x] += siz[y]; } } ll I = 0; void dfs2(ll x){ id[x] = I; I++; for(ll i = 1;i < (ll)G[x].size();i++){ if(siz[G[x][i]] > siz[G[x][0]]){ swap(G[x][i],G[x][0]); } } for(ll i = 0;i < (ll)G[x].size();i++){ ll y = G[x][i]; if(i == 0) root[y] = root[x]; else root[y] = y; par[y] = x; dfs2(y); } } vector O(300000,0),O_R(300000,0),A(800000,0),E(800000,0),R_L(800000),R_R(800000); // A は合計 void eval(ll x){ ll s = (O_R[R_R[x]] - O_R[R_L[x]]) % MOD; A[x] += (s * E[x]) % MOD; A[x] %= MOD; if(x < N){ E[x * 2] += E[x]; E[x * 2] %= MOD; E[x * 2 + 1] += E[x]; E[x * 2 + 1] %= MOD; } E[x] = 0; } void ue_update(ll x){ ll X = 0; while((x >> X) > 0) X++; while(X > 0){ X--; eval(x >> X); } } void reeval(ll x){ while(x > 0){ eval(x); if(x < N){ eval(x * 2); eval(x * 2 + 1); A[x] = (A[x * 2] + A[x * 2 + 1]) % MOD; } x /= 2; } } void add(ll l,ll r,ll x){ //cerr << "add("<