33OJ
登录 注册

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

[JAG 2026 Summer Camp #1] CPK! Remix

Problem Description

Kaguya spends her days enjoying parfaits and taking part in programming contests.

She has a string SS of length NN consisting of uppercase English letters. She may perform the following operation any number of times, including zero.

  • Choose an integer ii (1≤i≤N−21\le i\le N-2) such that SiSi+1Si+2S_iS_{i+1}S_{i+2} is one of CPK, CKP, and PCK. Replace SiSi+1Si+2S_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 SS by performing the operation any number of times, modulo 998 244 353998\,244\,353.

Input Format

The input consists of a single test case of the following format.

N
S

The first line contains an integer NN (1≤N≤1061\le N\le 10^6), representing the length of the string SS.

The second line contains a string SS of length NN consisting of uppercase English letters.

Output Format

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

9
CPKCKPPCK
63
34
CPKPARTICIPATEDINPCKWHILEEATINGCKP
45
15
CPKCPKCPKCPFKKK
63