---

1. 题意理解

我们有 $n$ 种牌，每种最多 $C$ 张（$C \le 1000$）。
初始已经有一些牌（$X \le 1000$ 种牌有初始数量 $a_i$）。
我们可以额外挑一些牌（每种最多挑到 $C$ 张），使得整组牌能分成若干“叠”，每叠是：

• 三张相同数字 $(i,i,i)$
• 三张连续数字 $(i,i+1,i+2)$

问有多少种可能的最终牌组（包括初始牌和额外挑的牌），使得它能被分完。

等价于：对于每种牌 $i$，设最终有 $b_i$ 张，满足 $a_i \le b_i \le C$，且 $\{b_i\}$ 能被拆分成若干 triples（三张相同或三张连续）。

---

2. 可拆分的充要条件

这是一个经典问题：
设 $x_i$ 是第 $i$ 种牌的数量。
考虑从 $1$ 到 $n$ 扫描，在位置 $i$，我们尽量用三张相同的消去一些，剩下的必须参与顺子。

更形式化地，设 $dp[i][r_1][r_2]$ 表示处理完前 $i$ 种牌，并且当前有 $r_1$ 张 $i-1$ 和 $r_2$ 张 $i$ 要用于和 $i+1$ 组成顺子，是否可能。
但这里我们只关心计数，不关心可行性。

---

2.1 模 3 余数条件

关键观察：
对于三张相同 $(i,i,i)$，它不依赖于相邻牌。
对于顺子 $(i,i+1,i+2)$，它涉及三种牌各一张。

如果我们只考虑顺子，问题就是：能否把序列分成若干长度为 3 的连续段，每段覆盖三个位置各一张牌。

这类似于用 1×3 的长条覆盖。

---

2.2 用生成函数方法

考虑从左到右扫描，记录状态：
设 $f_i(x)$ 表示处理到第 $i$ 种牌，并且当前有若干张牌要往后匹配顺子的情况。
但更常用的是记录 $r_i = x_i \bmod 3$ 以及需要前一张牌、前两张牌的数量等信息。

实际上，已知结论（类似麻将牌型判断）：
对于无限序列 $x_1,x_2,\dots$，可被三张相同或三张连续完全划分的充要条件是：
存在非负整数 $y_i, z_i$ 使得：

$$x_i = 3y_i + z_{i-2} + z_{i-1} + z_i$$

其中 $y_i$ 表示 $i$ 组成三张相同的次数，$z_i$ 表示顺子 $(i,i+1,i+2)$ 的数量。

---

3. 转化为生成函数

设 $F(t)$ 是序列 $\{x_i\}$ 的生成函数。
条件 $x_i = 3y_i + z_{i-2} + z_{i-1} + z_i$ 在生成函数中表现为：

$$F(t) \equiv (1+t+t^2) Z(t) \pmod{3}$$

因为 $z_{i-2} + z_{i-1} + z_i$ 的生成函数是 $(1+t+t^2) Z(t)$，而 $3y_i$ 在模 3 下为 0。

所以充要条件是：$F(t)$ 能被 $1+t+t^2$ 整除（在 $\mathbb{F}_3[t]$ 中）。

---

4. 模 3 多项式

在模 3 下，$1+t+t^2$ 是不可约多项式（在 $\mathbb{F}_3$ 上无根）。
整除条件意味着：在 $\mathbb{F}_3$ 上，$F(\omega)=0$，其中 $\omega$ 是 $1+t+t^2=0$ 的根，即本原三次单位根（在 $\mathbb{F}_3$ 的扩域中）。

所以条件等价于：

$$\sum_{i} x_i \omega^i = 0 \quad \text{在 } \mathbb{F}_{3^2} \text{ 中} $$

因为 $1+t+t^2$ 的根在 $\mathbb{F}_9$ 中。

---

5. 问题转化

我们要求 $b_i \in [a_i, C]$ 且 $\sum b_i \omega^i = 0$ 的方案数。

设 $m_i = C - a_i \ge 0$，则 $b_i = a_i + t_i$，$t_i \in [0, m_i]$。

条件变为：

$$\sum_{i=1}^n (a_i + t_i) \omega^i = 0$$ $$\sum_{i=1}^n t_i \omega^i = - \sum_{i=1}^n a_i \omega^i $$

记 $S = \sum_{i=1}^n a_i \omega^i$（已知常数），我们要：

$$\sum_{i=1}^n t_i \omega^i = -S$$

其中 $t_i \in [0, m_i]$。

---

6. 动态规划思路（小 n）

如果 $n$ 小，可以 DP：
设 $dp[i][r]$ 表示前 $i$ 种牌，当前和（在 $\mathbb{F}_9$ 中）为 $r$ 的方案数。
转移：

$$dp[i][r] = \sum_{t=0}^{m_i} dp[i-1][r - t \omega^i] $$

初始 $dp[0][0]=1$，答案 $dp[n][-S]$。

但 $n$ 可达 $10^{18}$，不能直接 DP。

---

7. 利用循环性质

$\omega$ 在 $\mathbb{F}_9$ 中，满足 $\omega^2 + \omega + 1 = 0$，且 $\omega^3=1$（在特征 3 下）。
实际上在 $\mathbb{F}_3$ 上，$\omega$ 的阶是 3？检查：$\omega^3 - 1 = (\omega-1)^3$ 在特征 3 下，所以 $\omega=1$ 是三重根？不对，我们弄错了。

在 $\mathbb{F}_3$ 上，$t^3 - 1 = (t-1)^3$，所以 1 是唯一的三次单位根。那么 $1+t+t^2$ 在 $\mathbb{F}_3$ 上不可约，它的分裂域是 $\mathbb{F}_9$，$\omega$ 在 $\mathbb{F}_9$ 中且 $\omega^3 = 1$ 不成立（因为那样 $\omega$ 会是 $t^3-1$ 的根，但 $t^3-1=(t-1)^3$ 在 $\mathbb{F}_3$ 上）。

所以 $\omega$ 的乘法阶是 8？检查：$\mathbb{F}_9^\times$ 是 8 阶循环群。所以 $\omega$ 的阶是 8。

因此 $\omega^i$ 的周期是 8（在 $\mathbb{F}_9^\times$ 中）。

---

8. 大 n 的解法

由于 $\omega^i$ 每 8 个一循环，我们可以把 $1..n$ 分成若干完整的周期（长度 8）和一段余数。

设 $n = 8q + r$，$0 \le r < 8$。

对于每个剩余类 $j \mod 8$，该剩余类中的位置 $i$ 对应的 $\omega^i$ 是相同的，记作 $\omega^j$。

这些位置上的 $t_i$ 是独立的，且上界 $m_i$ 可能不同（因为初始牌 $a_i$ 可能不同）。

---

9. 生成函数合并

对于每个剩余类 $j$，设该剩余类包含的位置集合为 $I_j$，每个位置 $i \in I_j$ 的 $t_i \in [0, m_i]$。

该剩余类的生成函数是：

$$G_j(x) = \prod_{i \in I_j} \left(1 + x^{\omega^j} + x^{2\omega^j} + \dots + x^{m_i \omega^j}\right) $$

这里 $x$ 是形式变量，但指数在 $\mathbb{F}_9$ 中运算，系数在 $\mathbb{Z}$ 中（模 $998244353$）。

我们要计算所有 $G_j(x)$ 的乘积中 $x^{-S}$ 的系数。

---

10. 具体计算

$\mathbb{F}_9$ 有 9 个元素，所以生成函数可以表示成长度 9 的向量（指数模 9 加法）。

对于每个剩余类 $j$，我们计算它的分布：
初始 $H_j[e] = 0$，$H_j[0]=1$。
对于该类的每个位置 $i$，更新：

$$H_j'[e] = \sum_{t=0}^{m_i} H_j[e - t \omega^j]$$

这里下标 $e$ 在 $\mathbb{F}_9$ 中，用 0..8 表示。

由于 $m_i \le C \le 1000$，直接卷积是 $O(9 \cdot m_i)$，对于 $|I_j|$ 个位置，复杂度 $O(9 \cdot C \cdot |I_j|)$。

---

11. 大 n 的处理

$n$ 很大，但 $X \le 1000$，意味着只有最多 1000 个位置有特殊上界（$m_i < C$），其余位置 $m_i = C$。

对于 $m_i = C$ 的位置，它们的生成函数相同，可以快速幂合并。

所以步骤：

1. 把 $1..n$ 按模 8 分成 8 个剩余类。
2. 对于每个剩余类，先计算所有 $m_i = C$ 的位置的生成函数 $P_j(x)$（用快速幂，因为相同生成函数的卷积幂可以快速计算）。
3. 再考虑 $m_i < C$ 的特殊位置（最多 1000 个），逐个乘到对应剩余类的生成函数中。

---

12. 最终算法框架

• 将 $n$ 分解为 $n = 8q + r$。
• 对 $j=0..7$，计算该剩余类的长度：
  若 $j \le r$，长度 $= q+1$，否则 $= q$。
• 对每个 $j$，先计算 $F_j = (1 + x^{\omega^j} + \dots + x^{C\omega^j})^{\text{长度}}$（用快速幂，但注意长度可能很大，但卷积在 $\mathbb{F}_9$ 上只有 9 个值，可以矩阵快速幂）。
• 对每个特殊初始牌 $(k_i, a_i)$，找到 $j = k_i \bmod 8$，从 $F_j$ 中扣除 $m_i = C-a_i$ 的部分（即除以 $1+\dots+x^{C\omega^j}$，再乘以 $1+\dots+x^{m_i\omega^j}$）。
• 所有 $F_j$ 卷积得到总分布，取 $-S$ 位置的系数。

---

13. 模运算

$\mathbb{F}_9$ 可以用 $\mathbb{F}_3[\alpha]/(\alpha^2+1)$ 表示，但这里我们只需用 0..8 表示 9 个元素，加法模 9 是指数运算，实际上我们在做循环卷积（模 $x^9-1$）。

所以生成函数乘法就是长度为 9 的循环卷积，可用 NTT 模 998244353 计算（但 9 很小，直接 $O(81)$ 卷积即可）。

---

14. 总结

这道题的核心是：

1. 将“可拆分成 triple”转化为在 $\mathbb{F}_9$ 上的线性条件。
2. 利用 $\omega^i$ 的周期 8 将大 $n$ 分解。
3. 对每个剩余类用生成函数和快速幂处理。
4. 特殊初始牌单独处理。

由于 $C \le 1000$ 且 $X \le 1000$，这个方法是可行的。