「LAOI-19」Unfair Fate

题号：NC315653
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 周朴园：谁指使你来的？
$\hspace{15pt}$ 鲁侍萍：（悲愤）命，不公平的命指使我来的！
$\hspace{15pt}$ ——曹禺《雷雨》

$\hspace{15pt}$ 给定两个字符串 $s,t$ ，下标从 $1$ 开始。
$\hspace{15pt}$ 设 $f(\texttt{str},l,r)$ 表示字符串 $\texttt{str}$ 中的第 $l$ 个字符开始到第 $r$ 个字符结束组成的连续子串， $k \times \texttt{str}$ 表示将 $k$ 个字符串 $\texttt{str}$ 依次首尾拼接得到的字符串。

$\hspace{15pt}$ 有 $Q$ 次操作，每次操作是以下两种类型：
$\hspace{23pt}\bullet\,$ 操作一，给定字符位置 $x$ 和字符 $c$ ，将 $s$ 的第 $x$ 个字符改为 $c$ 。修改是持久的，不相互独立。
$\hspace{23pt}\bullet\,$ 操作二，给定字符串子串区间 $l, r$ 和整数 $k$ ，求在字符串 $k \times f(s,l,r)$ 的所有 $2^{k(r-l+1)}$ 种子序列选取的方案中，等概率随机选取一种方案，使得选出的子序列是 $t$ 的子序列的概率（空序列是任意序列的子序列）。
$\hspace{30pt}$ 可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。更具体地，你需要找到一个整数 $x \in [0, M)$ 满足 $x \times q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。

【名词解释】
$\hspace{15pt}$ 子序列：从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

输入描述:

第一行输入一个仅由小写字母构成的字符串 。
第二行输入一个仅由小写字母构成的字符串 。
第三行输入一个非负整数 。
此后  行，第  行输入一个整数 ，表示第  次操作的类型，编号同题目描述。随后在同一行：
若 ，输入一个整数  和一个小写字母 ；
若 ，输入三个整数 。

输出描述:

对于每一次操作二，新起一行输出一个整数，表示概率对  取模后的结果。

示例1

输入

复制

unfairfate
fft
3
2 3 10 1
1 9 d
2 7 10 2

输出

复制

967049217
982646785

说明

对于第一次操作，询问字符串 ，该字符串有  种选取子序列的方式，合法的选择方案为：
；
；
；
；
；
；
；
不选的空序列。
共  种情况符合条件，所以概率为 ，对  取模后为 。

对于第二次操作，将  的第  个字符改为 ，即 。

对于第三次操作，询问字符串为 ，该字符串有  种选取子序列的方式，合法的选择方案为：
；
；
；
不选的空序列。
共  种情况符合条件，所以概率为 ，对  取模后为 。

示例2

输入

复制

distorteddream
sad
3
2 1 3 2
1 12 s
2 9 13 2

输出

复制

904658945
980697089

说明

对于第一次操作，询问字符串 ，该字符串有  种选取子序列的方式，共  种情况符合条件，所以概率为 。

对于第二次操作，将  的第  个字符改为 ，即 。

对于第三次操作，询问字符串 ，该字符串有  种选取子序列的方式，共  种情况符合条件，所以概率为 。

备注:

请注意常数因子在程序效率上带来的影响。
在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。