F - Inserting Process Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の英小文字列 T が与えられます。

以下の条件をすべて満たす文字列の列 s=(s_0,s_1,\ldots,s_N) の個数を 998244353 で割った余りを出力してください。

  • s_0 は空文字列
  • i=1,2,\ldots,N に対し、s_{i} は s_{i-1} の好きな位置（先頭や末尾でもよい）に好きな文字を 1 文字挿入することで得られる文字列
  • s_N=T

制約

  • 1\leq N\leq 22
  • N は整数
  • T は長さ N の英小文字列

入力

入力は以下の形式で標準入力から与えられる。

N
T

出力

答えを出力せよ。

入力例 1

3
aab

出力例 1

3

条件を満たす s は以下の 3 つです。

  • 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

Score : 500 points

Problem Statement

You are given a string T of length N consisting of lowercase English letters.

Output, modulo 998244353, the number of sequences of strings s=(s_0,s_1,\ldots,s_N) that satisfy all of the following conditions.

  • s_0 is an empty string.
  • For i=1,2,\ldots,N, the string s_{i} is obtained by inserting one arbitrary character at an arbitrary position (possibly beginning or end) in s_{i-1}.
  • s_N=T

Constraints

  • 1\leq N\leq 22
  • N is an integer.
  • T is a string of length N consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N
T

Output

Output the answer.

Sample Input 1

3
aab

Sample Output 1

3

The sequences s that satisfy the conditions are the following three:

  • s=(\texttt{""}, \texttt{"a"} ,\texttt{"aa"} ,\texttt{"aab"} )
  • s=(\texttt{""}, \texttt{"a"} ,\texttt{"ab"} ,\texttt{"aab"} )
  • s=(\texttt{""}, \texttt{"b"} ,\texttt{"ab"} ,\texttt{"aab"} )

Sample Input 2

7
atcoder

Sample Output 2

5040

Sample Input 3

22
atcoderbeginnercontest

Sample Output 3

115732070