题目描述

小 D 正在研究相似性。

小 D 认为两个等长字符串 $S$ 和 $T$ 是相似的，当且仅当将它们各删去一些字符后，它们变得一样了。

顾名思义，既然这两个字符串是相似的，那么这里的“一些”不能太多。具体而言，小 D 想了一个小阈值 $k$，认为如果删去的字符数不超过 $k$（两个字符串各不超过 $k$ 个），那么我们就认为这两个字符串的确是相似的。

小 D 想了一个长度为 $n$ 的大写字符串 $S$。他想要知道，在所有长度同样为 $n$ 的大写字符串中，和 $S$ 相似的有多少个呢？

但他并不会，请你帮帮他。因为这个答案可能很大，所以你只要求出答案对 $998244353$ 取模的结果即可。

输入格式

第一行一个字符串 $S$，表示小 D 想的字符串。

第二行一个整数 $k$，表示小 D 想的阈值。

输出格式

输出一行一个整数，表示与 $S$ 相似的字符串个数对 $998244353$ 取模的结果。

样例一

输入

GUGUA
1

输出

619

解释

我想到了一个绝妙的解释，可惜这里空白太小，写不下。

样例二

输入

GUUGUA
1

输出

746

样例三

见下发文件。

样例四

见下发文件。

限制与约定

对于所有测试数据：

• $1 \le n=|S| \le 3\times 10^4$；
• $0 \le k \le 4$；
• 保证 $S$ 仅由大写字母组成。

子任务：