P17529 [JAG 2026 Summer Camp #1] CPK! Remix

*Kaguya* spends her days enjoying *parfaits* and taking part in *programming contests*. She has a string $S$ of length $N$ consisting of uppercase English letters. She may perform the following operation any number of times, including zero. - Choose an integer $i$ ($1\le i\le N-2$) such that $S_iS_{i+1}S_{i+2}$ is one of `CPK`, `CKP`, and `PCK`. Replace $S_iS_{i+1}S_{i+2}$ with any one of `CPK`, `CKP`, and `PCK`. Find the number of distinct strings that can be obtained from $S$ by performing the operation any number of times, modulo $998\,244\,353$.

The input consists of a single test case of the following format. ```text N S ``` The first line contains an integer $N$ ($1\le N\le 10^6$), representing the length of the string $S$. The second line contains a string $S$ of length $N$ consisting of uppercase English letters.

Print the number of distinct strings that can be obtained from $S$, modulo $998\,244\,353$.