Problem Statement

A string x consisting of lowercase English letters is said to be good if and only if the following condition is satisfied.

• Every (contiguous) substring of x whose length is 2 or greater satisfies the following:
• no character occupies the majority of that substring.

For example, acbca is not good because c occupies the majority of the substring cbc.
You are given a string S of length N consisting of lowercase English letters and ?.
You want to replace each ? with a lowercase English letter of your choice to make S a good string.
Find the number of ways to make S a good string, modulo 998244353.

Input

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

Output

Print the answer.

Constraints

• $2 \leq N \leq 5000$
• S is a string of length N consisting of lowercase English letters and ?.

Sample Input 1

3
a?b

Sample Output 1

24

Every way other than aab and abb satisfies the condition.

Sample Input 2

3
a?a

Sample Output 2

0

Sample Input 3

20
ugsyakganihodnwmktgi

Sample Output 3

1

Sample Input 4

20
??a???h?m?y?ts???tl?

Sample Output 4

444225229

见题面 Input 部分

见题面 Output 部分