Charles 向 Ada 抱怨道：“那个济慈（Keats）！手稿里有这么多拼写错误！我该怎么把它们全改过来呢？”

Ada 回应道：“我这台引擎里有个程序能帮你。对于给定的单词，它会考虑细微的错误，并找出所有与该单词相近的词，这样就可以在英语词典中查到了。来，帮我拿一下茶，看好了。”

Ada 疯狂地打孔并穿好卡片，然后启动了引擎。蒸汽从锅炉中喷涌而出，引擎先是轻微地轰鸣，随后声音越来越大，震动着整个房间，直到最后，一个过载的凸轮卡住了，机器突然停止了运转。

“嗯，”Ada 沉思道，“我原以为这能行的。”

两个字符串之间的 Levenshtein 距离是指将一个字符串转换为另一个字符串所需的最少简单单字母操作次数。这些操作包括：

• 在字符串的任意位置添加一个字母。
• 删除字符串中任意位置的一个字母。
• 将字符串中的任意字母更改为其他任何字母。

给定一个由字母 ‘A’-‘Z’ 组成的输入字符串和一个 Levenshtein 距离。请输出与输入字符串的 Levenshtein 距离恰好为该距离的、由字母 ‘A’-‘Z’ 组成的不同字符串的数量。由于这个数字可能很大，请输出其对质数 $998,244,353$ 取模后的结果。

输入格式

输入包含一行，其中包含一个字符串 $s$ ($1 \le |s| \le 10$，$s$ 仅包含大写字母)，后跟一个空格，再跟一个整数 $d$ ($0 \le d \le 10$)，其中 $s$ 是目标字符串，$d$ 是感兴趣的 Levenshtein 距离。

输出格式

输出一个整数，表示与输入字符串 $s$ 的 Levenshtein 距离为 $d$ 的、由字母 ‘A’-‘Z’ 组成的不同字符串的数量，结果对 $998,244,353$ 取模。注意，空字符串也被视为一个有效的候选字符串。

样例

样例输入 1

ICPC 1

样例输出 1

230

样例输入 2

PROGRAMMER 10

样例输出 2

110123966