Both Reversible

AtCoder

IDarc171_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

4
?ba?

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`.

Input #2

10
?y?x?x????

Output #2

Input #3

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

Output #3

193994800

Input #4

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

Output #4

363594614

API Response (JSON)

{
  "problem": {
    "name": "Both Reversible",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc171_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string $T$ is called a **good string** when it satisfies the following condition:\n\n*   There is a pair of strings $(A, B)$ that satisfies all of the following:\n    *   Both $A$ and $B$ are non-empty...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments