{"problem":{"name":"ABC Ultimatum","description":{"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 len","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc055_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1\\le N \\le 15$.\n*   $S$ is a string of length $3N$, consisting of `A`, `B`, `C`, and `?`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc055_d","tags":[],"sample_group":[["1\n???","3\n\nThere are $3$ good strings you can obtain: `ABC`, `BCA`, and `CAB`."],["2\nAA????","2\n\nThere are $2$ good strings you can obtain: `AABBCC` and `AABCBC`."],["3\n?A?A?A?A?","0\n\nIt's impossible to obtain a good string, as there are already $4$ `A`'s."],["9\n?????????A??B??C???????????","331653164"]],"created_at":"2026-03-03 11:01:14"}}