← 返回题目列表

AtCoder · abc425_f

F. 插入过程

中文机器翻译题面 查看原题

分数: 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