AT_npcapc_2024_a Welcome to NPCAPC

对于仅由英文字母大写和小写字母组成、长度为 $N$ 的字符串，问有多少个字符串同时包含 `NPCAPC` 和 `npcapc` 这两个作为子序列（可以不连续），并将答案对 $998244353$ 取模。 给定 $T$ 组测试数据，请分别输出每组测试的答案。

输入通过标准输入给出，格式如下： > $T$ $\mathrm{Case}_1$ $\mathrm{Case}_2$ $\vdots$ $\mathrm{Case}_T$ 其中，$\mathrm{Case}_i$ 表示第 $i$ 组测试数据。每组测试数据格式如下： > $N$

共输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

## 部分得分 本题有多组部分分。 - 当 $N\leq 2\times 10^5,T\leq 10$ 的数据全部答对时，可以获得 $10$ 分。 - 当 $N\leq 10^9,T\leq 10$ 的数据全部答对时，可再获得 $10$ 分。 ## 样例解释 1 对于第 $1$ 组样例，满足条件的字符串如 `npcapcNPCAPC` 或 `NPCnpcAapPCc` 等，共有 $924$ 种。 ## 约束条件 - $1\leq N\leq 10^9$ - $1\leq T\leq 5000$ 由 ChatGPT 5 翻译