length of look and say sequence(作問コンテスト)

問題文

NにK回ラングレス圧縮した後の文字列長をmod998244353で求めよ

制約

• $K$は整数
• $N$は1,2,3,4,5,6,7,8,9からなる文字列　
• $1 \leq |N| \leq 1000$
• $1 \leq K \leq 10^{18}$
• Nに同じ数字が10個以上連続する区間はない

入力形式

出力形式

$N$に$K$回操作を施したものの桁数を$998244353$で割った余りを、1行で出力して下さい。

入力例1

1
10

出力例1

26

$N$は操作される度に $1 \rightarrow 11 \rightarrow 21 \rightarrow 1211 \rightarrow 111221 \rightarrow 312211$ $\rightarrow 13112221$
$\rightarrow 1113213211$
$\rightarrow 31131211131221$
$\rightarrow 13211311123113112211$
$\rightarrow 11131221133112132113212221$ と変化します。
$11131221133112132113212221$の桁数は$26$なので、$26$を出力します。
$312211$に操作することを例に考えます。
$312211$は、「1つの3,1つの1,2つの2,2つの1」と解釈できるので、操作後の数列は $13112221$ です。

入力例2

155554
1

出力例2

6

入力例3

998244353
998244353

出力例3

711578587