F - Both Reversible Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

文字列 T が次の条件を満たす時、T を 良い文字列 と呼びます。

  • 次の条件を全て満たす文字列の組 (A, B) が存在する。
    • A, B はともに空でない。
    • A + B = T
    • A + \mathrm{rev}(B) と \mathrm{rev}(A) + B はともに回文となる。

ここで A + B は文字列 A と文字列 B をこの順に結合してできる文字列を意味します。
また、\mathrm{rev}(A) は文字列 A の文字を逆順に並べ替えてできる文字列を意味します。

英小文字と ? からなる長さ N の文字列 S があります。
S に含まれる ? を英小文字に置き換える方法は 26^{(? の個数)} 通りありますが、そのうち置き換えた後の文字列が良い文字列になる方法は何通りありますか？答えを 998244353 で割った余りを求めてください。

制約

  • 2 \leq N \leq 5 \times 10^4
  • S は英小文字と ? からなる長さ N の文字列

入力

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

N
S

出力

問題文の条件を満たす置き換え方の個数を 998244353 で割った余りを出力せよ。

入力例 1

4
?ba?

出力例 1

1

文字列 abab は良い文字列です。なぜならば、A = ab, B = ab としたとき、A + B = abab であり A + \mathrm{rev}(B) = abba と \mathrm{rev}(A) + B = baab はともに回文となるからです。
S の ? を英小文字に置き換えてできる文字列のうち、良い文字列は abab の 1 通りのみです。

入力例 2

10
?y?x?x????

出力例 2

676

入力例 3

30
???a?????aab?a???c????c?aab???

出力例 3

193994800

入力例 4

36
????????????????????????????????????

出力例 4

363594614

Score: 1100 points

Problem Statement

A string T is called a good string when it satisfies the following condition:

  • There is a pair of strings (A, B) that satisfies all of the following:
    • Both A and B are non-empty.
    • A + B = T.
    • Both A + \mathrm{rev}(B) and \mathrm{rev}(A) + B are palindromes.

Here, A + B denotes the string formed by concatenating strings A and B in this order.
Also, \mathrm{rev}(A) denotes the string formed by reversing the order of the characters in string A.

There is a string S of length N consisting of lowercase English letters and the character ?.
Among the 26^{(\text{number of ?s})} ways to replace the ?s in S with lowercase English letters, how many result in a good string? Find the count modulo 998244353.

Constraints

  • 2 \leq N \leq 5 \times 10^4
  • S is a string of length N consisting of lowercase English letters and ?.

Input

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

N
S

Output

Print the number, modulo 998244353, of ways to replace the characters that satisfy the condition in the problem statement.

Sample Input 1

4
?ba?

Sample Output 1

1

The string abab is good, because if we set A = ab and B = ab, then A + B = abab, and both A + \mathrm{rev}(B) = abba and \mathrm{rev}(A) + B = baab are palindromes.
Among the strings that can be formed by replacing the ?s in S with lowercase English letters, there is only one good string, which is abab.

Sample Input 2

10
?y?x?x????

Sample Output 2

676

Sample Input 3

30
???a?????aab?a???c????c?aab???

Sample Output 3

193994800

Sample Input 4

36
????????????????????????????????????

Sample Output 4

363594614