※本問題文中に登場する東京農工大学は、実在する東京農工大学との関係はありません。

東京農工大学ではA、T、U から成る文字列 $S$ を「TUAT文字列」と定義し、これを用いて機密情報をやり取りしています。
あるとき、東京農工大学と対立する勢力である帝京濃江大学から攻撃を受け、文字列 $S$ の各文字に対して以下の操作が $X$ 回行われました。

• 操作 : その時点での $S$ に含まれる A、T、U の中からランダムに $1$ 文字を選び、それを $s$ とする。 $1$ 以上 $2 \times A$ 以下の整数 $x$ をランダムに選ぶ。このランダムに選ぶ行為はすべて独立に行う。これらを基に、次の規則に従って操作を行う。

  • A、T、Uそれぞれの文字に対して、次の表に示すように「似ている文字」、「似ていない文字1」、「似ていない文字2」を定める。

    	似ている文字	似ていない文字1	似ていない文字2
    A	4	7	V
    T	7	V	4
    U	V	4	7

  • $1 \le x \le 2 \times B$ ならば（言い換えると、 $\frac{B}{A}$ の確率で）、 $s$ を $s$ と「似ている文字」に書き換える。

  • $2 \times B + 1 \le x \le 2 \times B + (A - B)$ ならば（言い換えると、 $\frac{1}{2} \left( 1 - \frac{B}{A} \right)$ の確率で）、 $s$ を $s$ と「似ていない文字1」に置き換える。

  • $2 \times B + (A - B) + 1 \le x \le 2 \times A$ ならば（言い換えると、 $\frac{1}{2} \left( 1 - \frac{B}{A} \right)$ の確率で）、 $s$ を $s$ と「似ていない文字2」に置き換える。

• 例えば、 $s$ が A 、 $A = 3$ 、 $B = 2$ である場合、上記の規則に基づいて $x$ を決めたとき、 $1 \le x \le 4$ ならば 4 に、 $x = 5$ ならば 7 に、 $x = 6$ ならば V に置き換える。

$X$ 回の操作後の文字列 $T$ が与えられます。 $X$ 回の操作が行われる前の文字列 $S$ に TUAT という部分文字列が含まれる個数の期待値を $998244353$ で割った余りを求めてください。
ただし、 $S$ の部分文字列とは $S$ から $0$ 文字以上を取り除き、残った文字を元の順番で繋げたものを指します。また、異なる位置から取り出した部分文字列は区別されます。
期待値が有理数となる場合は、まずはその有理数を既約分数 $\frac{y}{x}$ の形で表し、 $xz \equiv y \pmod{998244353}$ を満たす $0$ 以上 $998244352$ 以下の整数 $z$ を求めてください。ただし、BeginningとEasyの部分点では期待値が整数となることが証明できます。

Final (65点)

• $0 \leq X \leq |T|$
• $1 \leq A \leq 10^7$
• $0 \leq B \leq A$
• $A \times B \gt 1$ であるとき、 $A$ と $B$ は互いに素
• $4 \leq |T| \leq 2 \times 10^5$ 、ただし $|T|$ は文字列 $T$ の長さを表す。
• $T$ は A、T、U、4、7、V から成る文字列
• $T$ に現れる 4、7、V の個数の和はちょうど $X$ に一致する

Hard (10点)

• Finalの制約に以下の制約を追加
• $0 \leq X \leq 5$

Normal (55点)

• Finalの制約に以下の制約を追加
• $0 \leq X \leq 5$
• $A = 3$
• $B = 1$

Easy (40点)

• Finalの制約に以下の制約を追加
• $X = 0$
• $A = 3$
• $B = 1$

Beginning (30点)

• Finalの制約に以下の制約を追加
• $X = 0$
• $A = 3$
• $B = 1$
• $4 \leq |T| \leq 2000$
• $T$ の $1$ 文字目と $|T|$ 文字目は T
• ある整数 $2 \leq P \leq |T| - 2$ が存在して、 $T$ の $2$ 文字目から $P$ 文字目は U、 $P + 1$ 文字目から $|T| - 1$ 文字目は A

$X$ 回の操作が行われる前の文字列 $S$ に含まれる部分文字列 TUAT の個数の期待値を $998244353$ で割った余りを出力し、最後に改行してください。