正の整数 $K$ と、$x$ の多項式 $f(x)$ が文字列 $S$ として与えられます。

最初 $x = 1$ として、次の操作を $K$ 回繰り返します。

• $x \gets f(x)$ と更新する。

$K$ 回繰り返した後の $x$ を $998$ で割った余りを求めてください。

ここで、$S$ は次のBNF表記の<expr>シンボルで表されます。

<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= <value> | <value> "^" <number>
<value> ::= <number> | "x"
<number> ::= 1以上10^9未満の整数　ただし先頭の 0 は省略される

記号はそれぞれ以下の意味を表します。

• x: $x$
• +: 足し算
• *: 掛け算、ただし足し算 + よりも先に計算される
• ^: 累乗、ただし足し算 + や掛け算 * よりも先に計算される

たとえば、以下の文字列は上の <expr>シンボルになり得ます。

• 998244353: $998244353$
• x+1: $x+1$
• x*x+2*x+1: $x \times x + 2 \times x + 1$
• 123+456*x^789: $123+456 \times x^{789}$

また、以下の文字列は <expr>シンボルになり得ません。

• -x
• 1/2
• 2x
• 2^x
• 2^3^4

• $1 \leq K \leq 10^{18}, K$ は整数
• $|S| \leq 100$
• $S$ は問題文のBNF表記における <expr>

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

1. (20点) $K = 1, ~~ S$ に *, ^ は含まれない。
2. (20点) $K \leq 10^4, ~~ S$ に ^ は含まれない。
3. (30点) $K \leq 10^4$
4. (30点) 追加の制約なし

入力は、以下の形式で標準入力から与えられる。

答えを $998$ で割った余りを1行で出力せよ。