分数: 500 点
问题陈述
给你一个字符串 T 长度 N 由小写英文字母组成。
输出,模数 998244353,字符串序列的数量 s=(s_0,s_1,\ldots,s_N) 满足以下所有条件。
- s_0 是一个空字符串。
- 对于 i=1,2,\ldots,N,字符串 s_{i} 是通过在任意位置(可能是开头或结尾)插入一个任意字符获得的 s_{i-1}.
- s_N=T
约束
- 1\leq N\leq 22
- N 是一个整数。
- T 是一个长度为的字符串 N 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N T
输出
输出答案。
示例输入 1
3 aab
示例输出 1
3
序列 满足条件的 s 有以下三个:
- s=(\texttt{""}, \texttt{"a"} ,\texttt{"aa"} ,\texttt{"aab"} )
- s=(\texttt{""}, \texttt{"a"} ,\texttt{"ab"} ,\texttt{"aab"} )
- s=(\texttt{""}, \texttt{"b"} ,\texttt{"ab"} ,\texttt{"aab"} )
示例输入 2
7 atcoder
示例输出 2
5040
示例输入 3
22 atcoderbeginnercontest
示例输出 3
115732070