假设S是N个 keyence 副本的串联。 考虑从S中删除零个或多个字符，并在不改变顺序的情况下连接剩余的字符以形成新的字符串S'。有$2^{7N}$ 种方法可以选择我们删除字符的位置。 其中，有多少使S'等于t？ 求计数模998244353 。
输入格式
输入两行，分别为N 和t
输出格式
打印选择删除字符位置的方法数，以便s'等于t ，取模998244353 。
样例
输入样例1 2 key 输出样例1 6样例解释1(假) s=keyencekeyence,有六种方法可以选择我们删除字符的位置，以便s'=key 。
输入样例2 2 ccc 输出样例2 0 输入样例3 100 keyneeneeeckyycccckkke 输出样例3 275429980
数据范围
对于35% 的数据，1≤N≤1000
对于100% 的数据，1≤N≤$10^{18}$,1≤|t|≤2.5$times 10^5$ ,保证t只包含c,e,k,n,y
大样例下载