問題文

英小文字のみからなる長さ $N$ の文字列 $S$ と正整数 $K$ が与えられます。

文字列 $x$ に対して以下のアルゴリズムにより生成される Brainfuck プログラムを $f(x)$ で表すことにします。

• $i = 1, 2, \dots, |x|$ について以下を順に行う。
  • $c$ を $x_i$ の ASCII 文字コード として、'+' を $c$ 回出力する。
  • '.' を出力する。
  • $i \neq |x|$ ならば '>' を出力する。

$\underbrace{f(f(\dots f(S)\dots))}_{f\ \text{が}\ K\ \text{個}}$ に含まれる '+', '.', '>' の個数それぞれを $998244353$ で割ったあまりで求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^{18}$
• $S$ は英小文字のみからなる長さ $N$ の文字列

入力

出力

'+', '.', '>' の順でスペース区切りに答えを出力してください。

サンプル

2 1
ab

195 2 1

"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++." には '+', '.', '>' がそれぞれ $195, 2, 1$ だけ含まれています。

10 3
helloworld

2167152 49835 49834

1 1
a

97 1 0

6 1000000000000000000
sample

847839672 167391335 167391334