Sekarang adalah tahun 2075. Saat merapikan arsip, Anda menemukan kembali koleksi lencana dari kontes ICPC Regional 2025, yang awalnya dibagikan oleh organisasi Universal Cup.

Satu set lengkap lencana UCup.

Namun, pada masalah ini, kita hanya mempertimbangkan himpunan bagian yang terdiri dari tiga warna.

Lencana Anda hanya tersedia dalam tiga warna berbeda: Ultramarine (u), Crimson (c), dan Periwinkle (p). Satu paket suvenir lengkap didefinisikan sebagai empat lencana yang muncul dalam urutan yang tepat: Ultramarine, lalu Crimson, lalu Ultramarine, lalu Periwinkle (ucup).

Koleksi Anda terdiri dari $4n$ lencana yang disusun dalam satu baris. Anda ingat dengan jelas bahwa pada tahun 2025, susunan ini merupakan kelompok sempurna (perfect batch):

• Barisan tersebut dapat dipartisi menjadi $n$ upabarisan (subsequence) yang saling lepas (yaitu, menggunakan setiap lencana tepat dalam satu upabarisan), sedemikian sehingga setiap upabarisan membentuk satu paket suvenir lengkap (ucup).

Namun, selama 50 tahun terakhir, beberapa lencana telah memudar sehingga warnanya tidak dapat dibedakan lagi. Posisi-posisi ini dinyatakan dengan ?.

Diberikan keadaan saat ini dari barisan lencana $S$, hitunglah banyaknya cara untuk memulihkan warna-warna yang memudar (?) menjadi salah satu dari u, c, atau p, sedemikian sehingga barisan yang dihasilkan adalah kelompok sempurna. Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Perhatikan bahwa suatu upabarisan dapat diperoleh dari sebuah string dengan menghapus nol atau lebih karakter tanpa mengubah urutan karakter yang tersisa. Sebagai contoh, ucp, c, dan ucup adalah upabarisan dari string ucup, sedangkan uucp bukan upabarisan dari string ucup.

Masukan

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 50$).

Baris kedua berisi sebuah string $S$ dengan panjang $4n$ yang terdiri dari karakter u, c, p, dan ?.

Keluaran

Keluarkan banyaknya cara untuk mengganti setiap ? pada $S$ dengan salah satu dari u, c, atau p, sehingga string yang dihasilkan menyatakan kelompok sempurna, diambil modulo $998\,244\,353$.

Contoh

Masukan 1

1
????

Keluaran 1

1

Masukan 2

1
ucup

Keluaran 2

1

Masukan 3

1
uucp

Keluaran 3

0

Masukan 4

1
uu?u

Keluaran 4

0

Masukan 5

2
????????

Keluaran 5

11

Masukan 6

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

Keluaran 6

437