Serval 是加帕里幼儿园的新生。
期中考试前一天晚上，Serval 在梦中见到了考试试卷和试卷答案。
Serval 梦中的考试试卷只有不定项选择题，题号从 1 开始标号，但是题目数量并不确定。一道不定项选择题只有 ABCD 四个选项，其答案是正确选项按字典序排列得到的非空字符串，这意味着一道不定项选择题至少有一个正确选项。例如 ABD 或者 C 可以是一道不定项选择题的答案，而 DA 以及 BB 不是。一张试卷的答案是不定项选择题答案连接而成的字符串。
梦醒之后，Serval 连忙写下了记忆中残留的答案片段。Serval 可能会修改写下的答案字符串，但他最好奇的是，对于某一段答案字符串，有多少份恰好包含 k 道不定项选择题的不同试卷，其答案恰为这个字符串。两份试卷不同当且仅当某道题号相同的不定项选择题的答案不同。
具体来说，Serval 写下了长度为 n 的仅包含 ABCD 的字符串 S。Serval 给出了 q 次操作，操作分为
以下两种：
1. 给出 l, r，对于 l ≤ x ≤ r，将 Sx 变为下一个选项，即 A 变为 B，B 变为 C，C 变为 D，D 变为 A。
2. 给出 l, r, k，对于 Sl
, Sl+1, . . . , Sr 依次连接得到的答案字符串，求出有多少份恰好包含 k 道不定项
选择题的不同试卷，其答案恰为这个字符串。
对于第二个操作，由于答案可能很大，你只需要求出答案对 998 244 353 取模的结果。
Serval 还是幼儿园的小朋友，并不能解决这个问题。你能帮他解决他的小问题，满足他的好奇心吗？
