Nous sommes en l'an 2075. En rangeant vos archives, vous avez redécouvert une collection de badges des concours régionaux ICPC 2025, distribués à l'origine par l'organisation Universal Cup.

Un ensemble complet de badges UCup.

Dans ce problème, cependant, nous ne considérons qu'un sous-ensemble de trois couleurs.

Vos badges se déclinent uniquement en trois couleurs distinctes : Outremer (u), Cramoisi (c) et Pervenche (p). Un pack souvenir complet est défini comme quatre badges apparaissant dans l'ordre exact : Outremer, puis Cramoisi, puis Outremer, puis Pervenche (ucup).

Votre collection se compose de $4n$ badges disposés sur une rangée. Vous vous souvenez très clairement qu'en 2025, cet arrangement formait un lot parfait :

• La séquence pouvait être partitionnée en $n$ sous-séquences disjointes (c'est-à-dire en utilisant chaque badge dans exactement une sous-séquence), de telle sorte que chaque sous-séquence formait un pack souvenir complet (ucup).

Cependant, au cours des 50 dernières années, certains badges se sont décolorés, rendant leurs couleurs indiscernables. Ces positions sont représentées par ?.

Étant donné l'état actuel de la séquence de badges $S$, calculez le nombre de façons de restaurer les couleurs effacées (?) en l'un des caractères u, c ou p, de sorte que la séquence résultante soit un lot parfait. Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.

Notez qu'une sous-séquence peut être obtenue à partir d'une chaîne en supprimant zéro ou plusieurs caractères sans changer l'ordre des caractères restants. Par exemple, ucp, c et ucup sont des sous-séquences de la chaîne ucup, tandis que uucp n'est pas une sous-séquence de la chaîne ucup.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 50$).

La deuxième ligne contient une chaîne $S$ de longueur $4n$ composée des caractères u, c, p et ?.

Sortie

Affichez le nombre de façons de remplacer chaque ? dans $S$ par l'un des caractères u, c ou p, de sorte que la chaîne résultante représente un lot parfait, modulo $998\,244\,353$.

Exemples

Entrée 1

1
????

Sortie 1

1

Entrée 2

1
ucup

Sortie 2

1

Entrée 3

1
uucp

Sortie 3

0

Entrée 4

1
uu?u

Sortie 4

0

Entrée 5

2
????????

Sortie 5

11

Entrée 6

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

Sortie 6

437