Problem Statement

Let's call a string $T$ of length $3N$, containing exactly $N$ letters A, $N$ letters B, and $N$ letters C, good, if it can be split into $N$ (not necessarily contiguous) subsequences of length $3$, so that the letters from each subsequence form ABC, BCA, or CAB.

You are given a string $S$ of length $3N$, consisting of characters A, B, C, and ?. Count the number of ways to replace each ? with one of A, B, and C, so that the resulting string is good. As this number can be very large, output it modulo $998244353$.

Constraints

• $1\le N \le 15$.
• $S$ is a string of length $3N$, consisting of A, B, C, and ?.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer modulo $998244353$.