题目描述

查尔斯向艾达抱怨道：“那个济慈！这份手稿里这么多拼写错误！我怎么可能把它们都改过来？”

艾达回答说：“我在分析机里写了一个程序可以帮你。对于给定的单词，它会考虑小的错误，并找出所有与该单词接近的单词，以便在英语词典中查找。来，帮我端着茶，看好了。”

艾达奋力地给卡片打孔穿线，然后启动了分析机。蒸汽从锅炉中喷涌而出，分析机先是轻柔地隆隆作响，然后越转越快，震得房间都在颤抖，直到最后一根过载的凸轮卡住，机器猛然停了下来。

“嗯，”艾达沉思道，“我还以为我已经解决了这个问题。”

两个字符串之间的莱文斯坦距离是指将一个字符串转换成另一个字符串所需的最少单字母操作次数。操作包括：

• 在字符串的任意位置插入一个字母。
• 删除字符串中任意位置的字母。
• 将字符串中的任意字母替换为其他字母。

给定一个由大写字母 'A'–'Z' 组成的输入字符串和一个莱文斯坦距离值。请输出所有与输入字符串的莱文斯坦距离恰好等于该值的不同字符串的数量。由于结果可能很大，请输出它对素数 $998,244,353$ 取模的结果。

输入格式

输入仅一行，包含一个字符串 $s$（$1 \le |s| \le 10$，$s$ 仅包含大写字母），后跟一个空格，再跟一个整数 $d$（$0 \le d \le 10$），其中 $s$ 是给定的字符串，$d$ 是目标莱文斯坦距离。

输出格式

输出一个整数，表示与输入字符串 $s$ 的莱文斯坦距离恰好为 $d$ 的不同字符串的数量（字符串由大写字母 'A'–'Z' 组成），对 $998,244,353$ 取模。注意，空字符串也视为有效的结果字符串。

ICPC 1

230

PROGRAMMER 10

110123966

提示

翻译由 DeepSeek V3.2 完成