給定一個僅含小寫字母的字符串 S ，問有多少個長度為 n 的僅含小寫字母的字符串中恰好出現(xiàn)了兩次 S 。答案對 998244353 取模。

輸入一行包含一個字符串 S 和一個整數(shù) n，用一個空格分隔。

輸出一行包含一個整數(shù)表示答案。

aba 6

53

【評測用例規(guī)模與約定】

對于 40% 的評測用例，n ≤ 20，|S | ≤ 6 ；

另有 10% 的評測用例，n ≤ 500，|S | ≤ 2 ；

對于 70% 的評測用例，n ≤ 10⁵ ；

對于所有評測用例，1 ≤ n ≤ 10⁹，1 ≤ |S | ≤ 30 。