지금은 2075년입니다. 기록 보관소를 정리하던 중, 당신은 원래 Universal Cup 조직에서 배포했던 2025 ICPC 리저널 대회의 배지 컬렉션을 다시 발견했습니다.

완전한 UCup 배지 세트.

하지만 이 문제에서는 세 가지 색상의 부분집합만 고려합니다.

당신의 배지는 울트라마린(u), 크림슨(c), 페리윙클(p)의 세 가지 뚜렷한 색상으로만 이루어져 있습니다. 완전한 기념품 팩은 울트라마린, 그다음 크림슨, 그다음 울트라마린, 마지막으로 페리윙클(ucup)의 정확한 순서로 나타나는 네 개의 배지로 정의됩니다.

당신의 컬렉션은 한 줄로 배열된 $4n$개의 배지로 구성되어 있습니다. 당신은 2025년에 이 배열이 완벽한 배치(perfect batch)였다는 것을 생생하게 기억합니다:

• 수열을 $n$개의 서로소인 부분수열로 분할하여(즉, 각 배지를 정확히 하나의 부분수열에 사용하여), 각 부분수열이 완전한 기념품 팩(ucup)을 이루도록 할 수 있었습니다.

그러나 지난 50년 동안 일부 배지의 색이 바래어 색상을 구별할 수 없게 되었습니다. 이러한 위치는 ?로 표시됩니다.

배지 수열의 현재 상태 $S$가 주어졌을 때, 바랜 색상(?)을 u, c, p 중 하나로 복원하여 결과 수열이 완벽한 배치가 되도록 하는 방법의 수를 계산하세요. 답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력합니다.

참고로 부분수열은 남은 문자들의 순서를 바꾸지 않고 문자열에서 0개 이상의 문자를 제거하여 얻을 수 있습니다. 예를 들어 ucp, c, ucup은 문자열 ucup의 부분수열이지만, uucp는 문자열 ucup의 부분수열이 아닙니다.

입력

첫 번째 줄에 정수 $n$ ($1 \le n \le 50$)이 주어집니다.

두 번째 줄에 문자 u, c, p, ?로 이루어진 길이 $4n$의 문자열 $S$가 주어집니다.

출력

$S$의 모든 ?를 u, c, p 중 하나로 대체하여 결과 문자열이 완벽한 배치를 나타내도록 하는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 출력합니다.

예제

입력 1

1
????

출력 1

1

입력 2

1
ucup

출력 2

1

입력 3

1
uucp

출력 3

0

입력 4

1
uu?u

출력 4

0

입력 5

2
????????

출력 5

11

입력 6

4
u???c???u???p???

출력 6

437