{"raw_statement":[{"iden":"problem statement","content":"A string $x$ consisting of lowercase English letters is said to be **good** if and only if the following condition is satisfied.\n\n*   Every (contiguous) substring of $x$ whose length is $2$ or greater satisfies the following:\n    *   no character occupies the majority of that substring.\n\nFor example, `acbca` is not good because `c` occupies the majority of the substring `cbc`.\nYou 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$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $S$ is a string of length $N$ consisting of lowercase English letters and `?`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"3\na?b"},{"iden":"sample output 1","content":"24\n\nEvery way other than `aab` and `abb` satisfies the condition."},{"iden":"sample input 2","content":"3\na?a"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"20\nugsyakganihodnwmktgi"},{"iden":"sample output 3","content":"1"},{"iden":"sample input 4","content":"20\n??a???h?m?y?ts???tl?"},{"iden":"sample output 4","content":"444225229"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}