#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 of length consisting of uppercase English letters. She may perform the following operation any number of times, including zero.
- Choose an integer () such that is one of
CPK,CKP, andPCK. Replace with any one ofCPK,CKP, andPCK.
Find the number of distinct strings that can be obtained from by performing the operation any number of times, modulo .
Input Format
The input consists of a single test case of the following format.
N
S
The first line contains an integer (), representing the length of the string .
The second line contains a string of length consisting of uppercase English letters.
Output Format
Print the number of distinct strings that can be obtained from , modulo .
9
CPKCKPPCK
63
34
CPKPARTICIPATEDINPCKWHILEEATINGCKP
45
15
CPKCPKCPKCPFKKK
63