← 返回题目列表

AtCoder · npcapc_2024_a

A. 欢迎来到NPCAPC

中文机器翻译题面 查看原题

配点 : 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