题目描述

给定一个仅含小写字母的字符串 $S$，问有多少个长度为 $n$ 的仅含小写字母的字符串中恰好出现了两次 $S$。答案对 $998\ 244\ 353$ 取模。

输入格式

输入一行包含一个字符串 $S$ 和一个整数 $n$，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

aba 6

53

aba 10

77907666

提示

对于 $40\%$ 的评测用例，$n \le 20$，$|S| \le 6$；
另有 $10\%$ 的评测用例，$n\le 500$，$|S| \le 2$；
对于 $70\%$ 的评测用例，$n\le 10^5$；
对于所有评测用例，$1\le n\le 10^9$，$1 \le |S| \le 30$。