{"raw_statement":[{"iden":"problem statement","content":"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`.\nYou 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$."},{"iden":"constraints","content":"*   $1\\le N \\le 15$.\n*   $S$ is a string of length $3N$, consisting of `A`, `B`, `C`, and `?`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"1\n???"},{"iden":"sample output 1","content":"3\n\nThere are $3$ good strings you can obtain: `ABC`, `BCA`, and `CAB`."},{"iden":"sample input 2","content":"2\nAA????"},{"iden":"sample output 2","content":"2\n\nThere are $2$ good strings you can obtain: `AABBCC` and `AABCBC`."},{"iden":"sample input 3","content":"3\n?A?A?A?A?"},{"iden":"sample output 3","content":"0\n\nIt's impossible to obtain a good string, as there are already $4$ `A`'s."},{"iden":"sample input 4","content":"9\n?????????A??B??C???????????"},{"iden":"sample output 4","content":"331653164"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}