根据你提供的代码，我来写题解并生成算法标签。

算法分析

问题理解

这是一个带约束条件的计数问题：

• 序列长度：$n$（可达 $10^9$）
• 每个数 $\leq m$（可达 $2\times 10^7$）
• 序列和是 $p$ 的倍数（$p \leq 100$）
• 至少有一个质数

核心算法：动态规划 + 矩阵快速幂 + 素数筛

算法思想

1. 补集转换

   • 总序列数（和是 $p$ 倍数） - 无非质数序列数（和是 $p$ 倍数）
   • 这样避免直接处理"至少一个质数"的复杂条件

2. 状态设计

   • $f[i]$：长度为当前考虑的数字个数，和模 $p$ 为 $i$ 的序列数（允许所有数字）
   • $g[i]$：长度为当前考虑的数字个数，和模 $p$ 为 $i$ 的序列数（只允许非质数）

3. 转移矩阵

   • 从模 $i$ 状态添加一个数字 $x$ 会转移到模 $(i + x) \bmod p$
   • 这可以用矩阵乘法描述

具体实现

1. 素数筛预处理

   • 使用线性筛标记质数
   • 同时统计两类数字：
     • sf[i%p]：所有数字中模 $p$ 为 $i$ 的数量
     • sg[i%p]：非质数中模 $p$ 为 $i$ 的数量

2. 矩阵快速幂

   • 初始状态：$f[0] = g[0] = 1$（空序列）
   • 转移矩阵就是 sf 和 sg 数组
   • 通过矩阵快速幂在 $O(p^3 \log n)$ 内计算 $n$ 次转移

3. 最终答案

   • 答案 = $f[0] - g[0]$（模 $p$ 为 $0$ 的序列数）

算法步骤

1. 读入 $n, m, p$
2. 线性筛统计模 $p$ 的各类数字数量
3. 构建转移矩阵 sf 和 sg
4. 矩阵快速幂计算 $n$ 次转移后的状态
5. 输出 $(f[0] - g[0]) \bmod 20170408$

复杂度分析

• 时间复杂度：$O(m + p^3 \log n)$
• 空间复杂度：$O(m + p)$

算法标签

• 动态规划
• 矩阵快速幂
• 素数筛法
• 模运算计数
• 补集原理

这个解法通过巧妙的数学建模，将序列计数问题转化为矩阵快速幂问题，能够高效处理 $n$ 高达 $10^9$ 的大规模情况，是组合计数问题的经典解法。