#include using namespace std; #define pii pair #define inf 1111111111 #define in(a) scanf("%d", &a) #define ins(a) scanf("%s", a) #define in2(a, b) scanf("%d%d", &a, &b) #define in3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define mp make_pair #define vi vector #define _ceil(n, a) ((n)%(a)==0?((n)/(a)):((n)/(a)+1)) #define cl clear() #define sz size() #define pn printf("\n") #define pr(a) printf("%d\n", a) #define prs(a) printf("%d ", a) #define pr2(a, b) printf("%d %d\n", a, b) #define pr3(a, b, c) printf("%d %d %d\n", a, b, c) #define pb push_back #define mem(a, b) memset((a), (b), sizeof(a)) #define all(X) (X).begin(), (X).end () #define iter(it, X) for (__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++) #define ext(a) {printf("%s\n", a); return 0;} #define oka(x, y) ((x)>=0&&(x)=0&&(y) _v = split(#args, ','); err(_v.begin(), args); pn;} vector split(const string& s, char c) { vector v; stringstream ss(s); string x; while (getline(ss, x, c)) v.emplace_back(x); return move(v); } void err(vector::iterator it) {} template void err(vector::iterator it, T a, Args... args) { cerr <>pos;} //typecast 1 in case of int //int on(int n, int pos) {return n | (1<=st && r<=ed) { tree[i].propagate(t); if (lc != rc) tree[lc].shift += t, tree[rc].shift += t; } else if (l>ed || r=st && r<=ed) { for (int x = 0; x < 26; x++) ans[x] += tree[i].cnt[x]; } else if (l>ed || r 0) { int temp = 1; for (j=0; j<26; j++) if (i!=j) temp = (temp * p[max(ans[j]-1, 0)]) % mod; temp = ( temp * ans[i] ) % mod; temp = ( temp * p[max(0, ans[i]-2)] ) % mod; sum += temp; sum %= mod; } } return sum; } int main() { int n, q, i, j, k, l, r, t, typ; p[0]=1; for (i=1; i