Hiện tại là năm 2075. Trong lúc sắp xếp lại kho lưu trữ của mình, bạn tình cờ tìm lại được bộ sưu tập huy hiệu từ các kỳ thi ICPC Khu vực năm 2025, ban đầu được phân phát bởi tổ chức Universal Cup.

Một bộ huy hiệu UCup đầy đủ.

Tuy nhiên, trong bài toán này, chúng ta chỉ xét một tập con gồm ba màu.

Các huy hiệu của bạn chỉ có ba màu phân biệt: Xanh lam sẫm (u), Đỏ thẫm (c), và Xanh dừa cạn (p). Một gói quà lưu niệm hoàn chỉnh được định nghĩa là bốn huy hiệu xuất hiện theo đúng thứ tự: Xanh lam sẫm, sau đó là Đỏ thẫm, tiếp theo là Xanh lam sẫm, rồi đến Xanh dừa cạn (ucup).

Bộ sưu tập của bạn gồm $4n$ huy hiệu được xếp thành một hàng. Bạn nhớ rất rõ rằng vào năm 2025, cách sắp xếp này là một lô hoàn hảo:

• Dãy có thể được phân hoạch thành $n$ dãy con rời nhau (tức là mỗi huy hiệu được sử dụng trong đúng một dãy con), sao cho mỗi dãy con tạo thành một gói quà lưu niệm hoàn chỉnh (ucup).

Tuy nhiên, qua 50 năm, một số huy hiệu đã bị phai màu khiến màu sắc của chúng không thể phân biệt được nữa. Những vị trí này được biểu thị bằng ?.

Cho trạng thái hiện tại của dãy huy hiệu $S$, hãy tính số cách khôi phục các màu bị phai (?) thành một trong các màu u, c, hoặc p, sao cho dãy thu được là một lô hoàn hảo. Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Lưu ý rằng một dãy con có thể được tạo ra từ một xâu bằng cách xóa đi không hoặc nhiều ký tự mà không làm thay đổi thứ tự của các ký tự còn lại. Ví dụ: ucp, c, và ucup là các dãy con của xâu ucup, trong khi uucp không phải là dãy con của xâu ucup.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 50$).

Dòng thứ hai chứa một xâu $S$ có độ dài $4n$ gồm các ký tự u, c, p, và ?.

Kết quả

In ra số cách thay thế mỗi dấu ? trong $S$ bằng một trong các ký tự u, c, hoặc p sao cho xâu thu được biểu thị một lô hoàn hảo, lấy phần dư theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

1
????

Kết quả 1

1

Dữ liệu vào 2

1
ucup

Kết quả 2

1

Dữ liệu vào 3

1
uucp

Kết quả 3

0

Dữ liệu vào 4

1
uu?u

Kết quả 4

0

Dữ liệu vào 5

2
????????

Kết quả 5

11

Dữ liệu vào 6

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

Kết quả 6

437