配点 : 100 点
問題文
由大小写字母组成的长度 在字符串 N 中, 计算同时包含NPCAPC 和 npcapc
作为子字符串的子字符串的数量(不必是连续的)。
您将获得 998244353 后求余数。
请解决
T 测试用例,因此请解决每个测试用例。
制約
- 1 \leq N\leq 10^9
- 1 \leq T\leq 5000
部分点
这个问题有多个部分点。 如果满足
- N \leq 2\times 10^5,T \leq 10 的数据集 10 点。 如果您正确回答
- N \leq 10^9,T \leq 10 的数据集的答案是正确的,则附加 这意味着第 10 点。 如果您正确回答
入力
输入将以以下格式从标准输入提供。
T
\mathrm{Case}_1
\mathrm{Case}_2
\vdots
\mathrm{Case}_T
这里 \mathrm{Case}_i 表示 i 个测试用例。每个测试用例均按以下格式给出。 打印第
N
出力
T 行。 打印第i 在线 一个整数,表示住在 i 个测试用例的答案。 在第
入力例 1
4 12 6 5839 123456
出力例 1
924 0 966252995 432934749
1 个测试用例中,满足条件的字符串为 npcapcNPCAPC 呀
问题文本中的 NPCnpcAapPCc 等
924 有一条街。
入力例 2
3 123456789 987654321 999999999
出力例 2
333574957 124462731 163251704