33OJ
登录 注册

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

[JAG 2026 Summer Camp #1] CPK! Remix

题目描述

辉夜(Kaguya)每天都在享用芭菲(parfaits)和参加程序设计竞赛(programming contests)中度过。

她有一个长度为 NN、由大写英文字母组成的字符串 SS。她可以执行以下操作任意次(包括零次):

  • 选择一个整数 ii(1≤i≤N−21\le i\le N-2),使得 SiSi+1Si+2S_iS_{i+1}S_{i+2} 是 CPK、CKP、PCK 中的一个。将 SiSi+1Si+2S_iS_{i+1}S_{i+2} 替换为 CPK、CKP、PCK 中的任意一个。

求从 SS 出发,执行任意次操作后能得到的不同字符串的数量,对 998 244 353998\,244\,353 取模。

输入格式

输入包含一组测试数据,格式如下:

N
S

第一行包含一个整数 NN(1≤N≤1061\le N\le 10^6),表示字符串 SS 的长度。

第二行包含一个长度为 NN、由大写英文字母组成的字符串 SS。

输出格式

输出从 SS 出发能得到的不同字符串的数量,对 998 244 353998\,244\,353 取模。

9
CPKCKPPCK
63
34
CPKPARTICIPATEDINPCKWHILEEATINGCKP
45
15
CPKCPKCPKCPFKKK
63