1. 题意理解

我们有一个数字串 $S$，长度 $n \le 500$。

定义 $f(x)$ 表示把整数 $x$ 拆分成若干个 $1 \sim m$ 的数的和的方案数（顺序不同视为不同方案）。
这其实就是：用 $1, 2, \dots, m$ 来组成 $x$ 的有序拆分的个数。

例如 $m=2$ 时，$f(4)=5$，因为：

$$4 = 1+1+1+1 = 2+1+1 = 1+2+1 = 1+1+2 = 2+2$$

$g(S)$ 的定义：
把数字串 $S$ 任意切成若干段（每段是一个数，允许前导零），把每段对应的整数加起来得到 $T$，然后计算 $f(T)$，并对所有切分方案求和。

例如 $S =$"123"：

• 切分 "$1|2|3$" → $1+2+3=6$，求 $f(6)$
• 切分 "$1|23$" → $1+23=24$，求 $f(24)$
• 切分 "$12|3$" → $12+3=15$，求 $f(15)$
• 切分 "$123$" → $123$，求 $f(123)$

$g(123) = f(6) + f(24) + f(15) + f(123)$

---

2. 先分析 $f(x)$ 的计算

$f(x)$ 是有序拆分成 $1 \dots m$ 的方案数。
这是一个经典的递推问题：

$$f(0) = 1 \quad (\text{空拆分})$$ $$f(k) = f(k-1) + f(k-2) + \dots + f(k-m), \quad k \ge 1 $$

其中 $f(k) = 0$ 当 $k < 0$。

解释：最后一步可以放 $1, 2, \dots, m$，所以从 $f(k-1)$ 等转移过来。

---

因为 $m \le 5$，这个递推是线性的，可以用矩阵快速幂来求 $f(x)$ 对 $998244353$ 取模的值。
但 $x$ 可能很大（字符串长度 $500$，数字总和最大是 $9 \times 500 = 4500$？不对，切分后加起来可能很大，因为一段可能是一个几百位数）。
例如 $S$ 全是 $9$，长度 $500$，那么 $T$ 最大可能是这个 $500$ 位数本身，即 $10^{500}$ 量级，不可能直接算 $f(T)$。

---

3. 关键观察

$f(x)$ 的递推是线性递推，模 $998244353$ 下，$f(x)$ 在 $x$ 很大时可以用矩阵快速幂计算，但 $x$ 可能极大（几百位十进制数），直接对 $x$ 做快速幂不行。
但是，线性递推在模 $p$ 下具有周期性，并且 $f(x)$ 可以表示成矩阵 $M$ 的 $x$ 次幂的形式。

设：

$$F_k = \begin{bmatrix} f(k) & f(k-1) & \dots & f(k-m+1) \end{bmatrix}^T $$

那么：

$$F_k = M \cdot F_{k-1}$$

其中 $M$ 是 $m \times m$ 矩阵：

$$M = \begin{bmatrix} 1 & 1 & 0 & 0 & \dots & 0 \\ 1 & 0 & 1 & 0 & \dots & 0 \\ 1 & 0 & 0 & 1 & \dots & 0 \\ \vdots & & & & \ddots & \vdots \\ 1 & 0 & 0 & \dots & 0 & 1 \\ 1 & 0 & 0 & \dots & 0 & 0 \end{bmatrix} $$

（第一列全是 $1$，次对角线下方的 $1$ 的位置对应递推）

更准确地说，对于 $m$：

$$M_{1,j} = 1 \ (1 \le j \le m),\quad M_{i,i-1} = 1 \ (2 \le i \le m),\ 其余为 0 $$

检查一下：
$F_k[1] = f(k) = f(k-1) + f(k-2) + \dots + f(k-m)$ 对应第一行全 $1$。
$F_k[i] = f(k-i+1) = F_{k-1}[i-1]$ 对应 $M_{i,i-1}=1$。

---

于是：

$$F_x = M^x \cdot F_0$$

其中 $F_0 = [1, 0, 0, \dots, 0]^T$。

所以 $f(x) = (M^x)_{1,1}$（因为 $F_x[1] = (M^x \cdot F_0)[1] = (M^x)_{1,1}$）。

---

4. 问题转化为：对所有切分方案，求 $M^{\text{sum}}$ 的 $(1,1)$ 元素之和

设一种切分方式得到的各段数值为 $a_1, a_2, \dots, a_t$，则 $T = a_1 + a_2 + \dots + a_t$。

我们要的是：

$$\sum_{\text{partition}} (M^{a_1 + a_2 + \dots + a_t})_{1,1} $$

---

注意矩阵幂的性质：
$M^{a+b} = M^a \cdot M^b$。

所以：

$$M^{a_1 + \dots + a_t} = M^{a_1} \cdot M^{a_2} \cdots M^{a_t} $$

我们要求的是这个乘积的 $(1,1)$ 元素的和。

---

5. 动态规划

设 $dp[i]$ 表示考虑前 $i$ 个字符的所有切分方式下，矩阵乘积的和（一个 $m \times m$ 矩阵）。

初始：$dp[0] = I$（单位矩阵）。

转移：
$dp[i] = \sum_{j=0}^{i-1} dp[j] \cdot M^{\text{num}[j+1:i]}$

其中 $\text{num}[j+1:i]$ 是子串 $S[j+1..i]$ 对应的整数。

---

最终答案 = $dp[n]$ 的 $(1,1)$ 元素。

因为 $n \le 500$，直接做是 $O(n^3 m^3)$ 会太大（矩阵乘法 $m^3$ 但 $m$ 很小，主要是 $n^3$ 大）。
需要优化：$\text{num}[j+1:i]$ 可能很大，但 $M^{\text{num}}$ 是在模 $998244353$ 下，且指数可对矩阵的阶取模？
矩阵在模 $p$ 下的阶至多是 $p^m - 1$ 量级，但 $p$ 很大，不能直接降指数。

---

6. 大指数矩阵快速幂

对于 $M^{\text{num}}$，其中 $\text{num}$ 是几百位十进制数，我们可以用十进制矩阵快速幂：
预处理 $M^1, M^{10}, M^{100}, \dots$，然后按数字位乘起来。

这样计算 $M^{\text{num}}$ 是 $O(\text{len} \cdot m^3)$，len 是 num 的位数。

---

7. 最终算法

1. 预处理 $M$ 的 $10^k$ 次幂，$k=0..n$。
2. DP：
   $dp[0] = I$
   对于 $i=1..n$：
   $dp[i] = 0$（矩阵）
   对于 $j=i-1..0$：
   $num$ = 子串 $S[j+1..i]$ 对应的整数（可能很大，但我们用十进制矩阵快速幂算 $M^{num}$）
   $dp[i] \ += dp[j] \cdot M^{num}$
3. 输出 $dp[n][1,1]$。

---

复杂度：$O(n^3 m^3 \log ?)$ 还是大，但 $n=500$ 时 $n^3=1.25\times 10^8$，不可行。
需要优化：注意到从 $j$ 到 $i$，$num$ 是 $num_{j+1,i} = num_{j+1,i-1} \times 10 + (S[i] - '0')$。
我们可以从小到大枚举 $i$，同时维护 $M^{num_{j,i}}$，这样不用每次都做十进制快速幂。

---

具体：
对每个 $j$，维护 $P_j = M^{\text{num}[j+1..i]}$，当 $i$ 增加时，$P_j = P_j^{10} \cdot M^{S[i]-'0'}$。
但 $P_j^{10}$ 还是需要做矩阵快速幂（$10$ 次幂很快，因为 $m$ 小）。

这样每步是 $O(n m^3 \log 10)$，总 $O(n^2 m^3 \log 10)$，可过。

---

8. 总结

算法步骤：

• 定义 $m \times m$ 转移矩阵 $M$。
• $dp[i]$ 是 $m \times m$ 矩阵，表示前 $i$ 个字符的所有切分对应的矩阵乘积之和。
• 初始 $dp[0] = I$。
• 对 $i=1..n$：
  • 初始化 $dp[i]$ 为零矩阵。
  • 对 $j=0..i-1$：
    • 计算 $M^{\text{num}[j+1..i]}$，利用上一步的 $M^{\text{num}[j+1..i-1]}$ 做 $(\ )^{10} \cdot M^{d}$。
  • 更新 $dp[i] += dp[j] \cdot \text{mat}$。
• 输出 $dp[n][1,1]$。