Background

Alice is a rabbit who likes symmetry.
Now she appoints you to help paint a wall.

There is a wall now, and string $a$ represents the color at each position.
The desired result is represented by string $b$. The character set is lowercase letters.

You may perform any number of operations. Each time, choose a sub-interval of $a$ with length $L$ and a string $c$ with length $L$, and assign that interval to be $c$.
For efficiency reasons, the $L$ you choose must satisfy $L \ge 3$.
For symmetry reasons, the string you choose must be an odd-length palindrome.
If you can finish this task, you will get a reward of $220$ “feilin” (pinyin: 菲林)!

Alice has fixed the colors of some positions, and marks the unfixed ones with ?. You want to know how many possible values of $b$ allow you to get the reward.
Alice reminds you that this number is too large, so you decide to take it modulo $998244353$.

Problem Description

Formal statement:
The character set is lowercase letters.
Given strings $a, b$ of length $n$, define one operation as choosing a sub-interval $[l, r]$ of $a$ whose length is odd and $\ge 3$, and assigning it to be a palindrome string.
If $a$ can be transformed into $b$ through a finite number of operations, then $a$ is called “good”.

Now you are given $a$ and a string $b$ consisting of lowercase letters and ? (note that the number of ? can be any integer in $[0, n]$). If each ? in $b$ can be replaced by any lowercase letter, how many possible assignments make $a$ “good”?

Output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $n$, the length of the strings.
The second line contains a string $a$ of length $n$, consisting only of lowercase letters.
The third line contains a string $b$ of length $n$, consisting of lowercase letters and ?.

Output Format

Output one integer, the number of valid assignments modulo $998244353$.

5
alice
alic?

2

Hint

This problem uses bundled testdata.

::cute-table{tuack} | Subtask | $n\le$ | Special Property | Score | |:-:|:-:|:-:|:-:| | $1$ | $5$ | None | $10$ | | $2$ | $10^5$ | $b$ contains only lowercase letters | $10$ | | $3$ | $10^5$ | $b$ contains only ? | $20$ | | $4$ | $2 \times 10^3$ | None | $20$ | | $5$ | $10^6$ | None | $40$ |

Translated by ChatGPT 5