問題文

$0,1,2$ と関数 ${\rm max,mex}$ から成る正しい式 $S$ があります。

ここでの正しい式、及びその式の値の定義は次の通りです。

• 数字0,1,2は正しい式であり、その値は（数としての）その数字である。
• $A,B$ が正しい式のとき、max($A$,$B$)は正しい式であり、その値は $A,B$ の値のうちの大きい方である。
• $A,B$ が正しい式のとき、mex($A$,$B$)は正しい式であり、その値は $A,B$ の値のいずれとも一致しない最小の非負整数である。
• 正しい式は上記のものに限る。

例えばmex(max(1,2),max(0,0)) は正しい式で、その値は ${\rm mex}({\rm max}(1,2),{\rm max}(0,0)) = {\rm mex}(2,0) = 1$ です。

いたずら好きのyukiさんは $S$ に含まれる 0,1,2,a,e のうち、0文字以上を?に変えてしまいました。

変更後の $S$ と整数 $K$ が与えられるので、式の値が $K$ であるような元の正しい式としてあり得るものは何通りかを求めてください。

答えは非常に大きくなることがあるため、 $998244353$ で割った余りを出力してください。

入力

$S$
$K$

• $1 \leq |S| \leq 2 \times 10^5$
• $S$ は問題文中の正しい式の0,1,2,a,e のうち、0文字以上を?に変更した文字列
• $K = 0,1,2$

出力

式の値が $K$ であるような元の正しい式としてあり得るものの個数を $998244353$ で割った余りを出力してください。

サンプル

m?x(1,2)
0

1

max(?,mex(0,?))
2

5

m?x(m?x(m?x(?,?),m?x(?,?)),m?x(m?x(?,?),m?x(?,?)))
1

250269

0
1

0