It is the year 2075. While organizing your archives, you rediscovered a collection of badges from the 2025 ICPC Regional contests, originally distributed by the Universal Cup organization.
A complete UCup badge set.
In this problem, however, we only consider a subset of three colors.
Your badges come in three distinct colors only: Ultramarine (u), Crimson (c), and Periwinkle (p). A complete souvenir pack is defined as four badges appearing in the exact order: Ultramarine, then Crimson, then Ultramarine, then Periwinkle (ucup).
Your collection consists of $4n$ badges arranged in a row. You vividly recall that in 2025, this arrangement was a perfect batch:
- The sequence could be partitioned into $n$ disjoint subsequences (i.e., using each badge in exactly one subsequence), such that each subsequence formed a complete souvenir pack (
ucup).
However, over the last 50 years, some badges have faded, making their colors indistinguishable. These positions are represented by ?.
Given the current state of the badge sequence $S$, calculate the number of ways to restore the faded colors (?) to one of u, c, or p, such that the resulting sequence is a perfect batch. As the answer may be large, output it modulo $998\,244\,353$.
Note that a subsequence can be derived from a string by removing zero or more characters without changing the order of the remaining characters. For example, ucp, c, and ucup are subsequences of the string ucup, while uucp is not a subsequence of the string ucup.
Input
The first line contains an integer $n$ ($1 \le n \le 50$).
The second line contains a string $S$ of length $4n$ consisting of characters u, c, p, and ?.
Output
Output the number of ways to replace every ? in $S$ with one of u, c, or p, so that the resulting string represents a perfect batch, taken modulo $998\,244\,353$.
Examples
Input 1
1 ????
Output 1
1
Input 2
1 ucup
Output 2
1
Input 3
1 uucp
Output 3
0
Input 4
1 uu?u
Output 4
0
Input 5
2 ????????
Output 5
11
Input 6
4 u???c???u???p???
Output 6
437