[小剧场]
终于有可做的题目了（泪流满面
欸提交到原题上怎么还是错的？
（大怒，求助AI
然后发现线段树 build(1, 0)，就这样死掉了。
题目都放在题单了，这里不放了
[A]
非常可做！
非常难调！
首先注意到 $si \geq s{i + 1}的话必定会在此处切一刀（就是这两个选项属于两个不同的题目），这是显然的，我们称这样的i$ 为断点。
然后，假设我们知道 [l, r) 间已有的断点个数，记为 s，答案是 \binom{r – l – s}{k – 1 – s}
考虑如何维护这个东西，应该第一眼是线段树
查询就直接区间查询，做完了（吗？
考虑修改 [l, r] 时候造成了什么影响
首先 [l, r) 内的断点会增加也会减少，这个增加量/减少量是什么呢？
答案是，如果维护这个区间目前的 XD 和 DX 数量（X 是不同于 D 的字符），将前者记为 s1, 后者记为 s2, 则 s’ = s + s1 – s2（想一想，应该很快就会发现）
但是只维护 DX 和 XD 是明显不够的，毕竟修改不是仅仅进行一轮，字母会轮换式的变动。
因此考虑对于 ABCD 每一个字母 ，都维护一个类似结构的数量，修改时候也只要也只要随字母轮换式变动就行。
但是，这是区间内的情况，更为棘手的是端点处，毕竟 $s{l – 1}和s{r + 1}$ 并不会随着变动。
我们考虑单独写一个单点修改，用于处理 l – 1 和 r 这两点的情况（这里没打错，结合上面 断点 的定义）
处理这两个点时候可能需要比对相邻两个现在字符是多少，这个直接维护在线段树内也行，另外开树状数组也行（别问我为什么选择了后者，因为贪图常数快），这个维护就是普通的区间加单点查询。
然后做完了，注意边界细节，以上的小剧场这是这一题真实发生的事情。
后面在上面 CQ1Z 的同学每次修改 [l,r) 至多只会让答案造成 ±2 的改变，这是完全正确的。
所以我不知道我在做什么，更不知道讲题的维护 4 \times 4 的矩阵在做什么。
理论上这题代码没那么长，不知道我干什么了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const LL mod = 998244353;
int n, m;
char str[N];
LL fac[N], inv[N];
struct node
{
int l, r, sum, tag;
int cnt[3][5];
//0 -> ?X (? != x) ?D 产生断点
//1 -> X? (X != ?) D? 消除断点
}tr[N << 2];
int BIT[N];
int lowbit(int x){return x & (-x);}
void add(int x, int v)
{
for (; x <= n; x += lowbit(x))BIT[x] += v;
}
int query(int x)
{
int res = 0;
for (; x; x -= lowbit(x))res += BIT[x];
return res;
}
LL quick_power(LL a, LL b)
{
LL res = 1;
while (b)
{
if (b & 1)res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
for (int i = 0; i < 4; i ++)
{
tr[u].cnt[0][i] = tr[u << 1].cnt[0][i] + tr[u << 1 | 1].cnt[0][i];
tr[u].cnt[1][i] = tr[u << 1].cnt[1][i] + tr[u << 1 | 1].cnt[1][i];
}
}
void build(int u, int l, int r)
{
if (l > r)return;
tr[u] = {l, r, 0, 0};
if (l == r)
{
tr[u].sum = (str[l] >= str[l + 1]);
if (str[l] != str[l + 1])
{
tr[u].cnt[0][str[l] - 'A'] ++;
tr[u].cnt[1][str[l + 1] - 'A'] ++;
}
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void trans(int u)
{
tr[u].sum = tr[u].sum + tr[u].cnt[1][3] - tr[u].cnt[0][3];
int c0 = tr[u].cnt[0][3], c1 = tr[u].cnt[1][3];
for (int i = 3; i; i --)
{
tr[u].cnt[0][i] = tr[u].cnt[0][i - 1];
tr[u].cnt[1][i] = tr[u].cnt[1][i - 1];
}
tr[u].cnt[0][0] = c0, tr[u].cnt[1][0] = c1;
}
void pushdown(int u)
{
tr[u].tag %= 4;
if (!tr[u].tag)return;
tr[u << 1].tag += tr[u].tag;
tr[u << 1].tag %= 4;
tr[u << 1 | 1].tag += tr[u].tag;
tr[u << 1 | 1].tag %= 4;
while (tr[u].tag --)
{
trans(u << 1);
trans(u << 1 | 1);
}
tr[u].tag = 0;
}
void modify(int u, int l, int r)
{
if (l < 1 || l >= n || r < 1 || r >= n)return;
if (l <= tr[u].l && tr[u].r <= r)
{
trans(u);
tr[u].tag ++;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)modify(u << 1, l, r);
if (mid < r)modify(u << 1 | 1, l, r);
pushup(u);
}
void modifyP(int u, int pos)
{
if (pos < 1 || pos >= n)return;
if (tr[u].l == tr[u].r)
{
for (int i = 0; i < 4; i ++)tr[u].cnt[0][i] = tr[u].cnt[1][i] = 0;
int a = (str[pos] - 'A' + query(pos)) % 4, b = (str[pos + 1] - 'A' + query(pos + 1)) % 4;
tr[u].sum = (a >= b);
if (a != b)
{
tr[u].cnt[0][a] ++;
tr[u].cnt[1][b] ++;
}
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (pos <= mid)modifyP(u << 1, pos);
else modifyP(u << 1 | 1, pos);
pushup(u);
}
int query(int u, int l, int r)
{
if (l < 1 || l >= n || r < 1 || r >= n)return 0;
if (l <= tr[u].l && tr[u].r <= r)return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1, sum = 0;
if (l <= mid)sum += query(u << 1, l, r);
if (mid < r)sum += query(u << 1 | 1, l, r);
return sum;
}
LL C(int a, int b)
{
if (a < 0 || b < 0 || a < b)return 0;
else return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int main()
{
scanf("%d%d%s", &n, &m, str + 1);
fac[0] = 1;
for (int i = 1; i <= n; i ++)fac[i] = fac[i - 1] * i % mod;
inv[n] = quick_power(fac[n], mod - 2);
for (int i = n - 1; ~i; i --)inv[i] = inv[i + 1] * (i + 1) % mod;
build(1, 1, n - 1);
while (m --)
{
int op, l, r, k;
scanf("%d%d%d", &op, &l, &r);
if (op == 1)
{
add(l, 1);
add(r + 1, -1);
modify(1, l, r - 1);
if (l > 1)modifyP(1, l - 1);
if (r < n)modifyP(1, r);
}
else if(op == 2)
{
scanf("%d", &k);
if (k > r - l + 1)puts("0");
else if(l == r)
{
if (k == 1)puts("1");
else puts("0");
}
else
{
int d = query(1, l, r - 1);
printf("%lld\n", C(r - l - d, k - 1 - d));
}
}
}
return 0;
}