题意三句话
① 只允许用前 $k$ 个小写字母。
② 给你一个长度 $n$ 的原串，你必须在它尾巴上再拼 $m$ 个字母（拼什么由你决定，只能用那 $k$ 个）。
③ 目标是让最终串拥有的「本质不同的子序列」数量最大，输出这个最大值（含空串，模 $10^9+7$）。
② 给你一个长度 $n$ 的原串，你必须在它尾巴上再拼 $m$ 个字母（拼什么由你决定，只能用那 $k$ 个）。
③ 目标是让最终串拥有的「本质不同的子序列」数量最大，输出这个最大值（含空串，模 $10^9+7$）。
子序列 = 挑若干个位置、保持顺序取出的字符（可以跳着挑）；按内容去重，同一个内容不管有几种挑法都只算一次。
动手玩：自己填字母，看总数怎么变
最终串：
本质不同子序列（含空串）
0
本质不同子串（含空串，对比用）
0
理论最优（贪心答案）
0
玩一玩这些问题：
· 把 $m$ 个槽全填
· 新字母用完后，第二个该填谁——刚用过的？还是最久没用的？
· 试着把
· 把 $m$ 个槽全填
a，再全填没见过的新字母，差多少？为什么？· 新字母用完后，第二个该填谁——刚用过的？还是最久没用的？
· 试着把
ba（$m=2,k=3$）推到 15 条，看看你选的追加串是不是 cb。
计数 DP 的真相：每读一个字符 = 把口袋「复印 + 贴尾巴」
设 $T$ = 当前所有本质不同子序列的集合（含空串），$|T|$ 就是口袋大小。
追加字符 $c$ 时，集合的变化恰好是 $$T\ \longrightarrow\ T\ \cup\ \{\,t+c\;:\;t\in T\,\}$$ ——把整个口袋复印一份，每条尾巴贴上 $c$，再塞回去。理论新增 $|T|$ 条，但塞回时会撞车（内容早已存在），只有没撞上的才是新住户。
追加字符 $c$ 时，集合的变化恰好是 $$T\ \longrightarrow\ T\ \cup\ \{\,t+c\;:\;t\in T\,\}$$ ——把整个口袋复印一份，每条尾巴贴上 $c$，再塞回去。理论新增 $|T|$ 条，但塞回时会撞车（内容早已存在），只有没撞上的才是新住户。
① 位置轴：$last[i]$ 与求和区间 $[\,last[i],\ i-1\,]$
② 记账本（每个字母一个快照 $G[c]$）
③ 复印现场：这一条是「新增」还是「撞车」？撞的那条最早住在哪里？
新增 $f[i]$ 条（$=|T|_{\text{旧}} - G[c]$）
撞车 $G[c]$ 条（正是上次快照里那批 → 这就是减数的来源）
④ 线性 DP 表：$f[i]=g[i-1]-g[last[i]-1]$，$g[i]=g[i-1]+f[i]$
追加 $m$ 个字符：每一步都喂「最饿」的那个字母
新增条数 $=|T|_{\text{旧}} - G[c]$。这里 $|T|_{\text{旧}}$ 对所有候选字母都一样，所以 $G[c]$ 越小越赚。
而在精确整数下口袋只增不减，$G[c]$ 小 $\iff$ 上次用 $c$ 的时刻早 $\iff$ 这个字母最久没出场（从没用过的 $G=0$，排最前）。
而在精确整数下口袋只增不减，$G[c]$ 小 $\iff$ 上次用 $c$ 的时刻早 $\iff$ 这个字母最久没出场（从没用过的 $G=0$，排最前）。
① 候选牌桌（新增 $=|T|-G[\cdot]$，绿色为当前最优）
平局（几个字母 $G$ 相同）随便选哪个，最终条数完全一样：被选中的那个 $G$ 立刻跳到 $|T|$（最饱），另一个下一轮就被选中，轮换顺序换了但总量轨迹不变。
② 口袋与记账
已追加的串：
当前含空串的本质不同子序列数
对照实验：贪心的比较键不能取模（这就是只过 13 个点的原因）
$P$ 和 $G$ 一旦超过 $10^9+7$ 就绕回小数，「$G$ 值小」就不再等于「最久未用」。正确写法：比 last[]（精确出场序号，永不溢出），不比取模后的 $G$。
样例自测（可全部手推核对）
答案含空串。前 3 组是题面/下发样例口径，后面是从 $2^m$ 暴力和大整数基准双向验证过的自造小样例。
暴力的作用范围
想自验，就写一个 集合暴力：$T=\{\varepsilon\}$，逐个字符做
T |= {t + ch for t in T}，最后输出 |T|；
再枚举前 $k$ 个字母的所有长度 $m$ 组合取最大。串长 $\le 20$ 完全够用，正好用来对拍你的 DP。标程（$O((n+m)\cdot k)$，空间 $O(k)$）
两个会把答案打崩的细节
- 比模值选字母：小点全对、大点全错（$m\ge 30$ 左右就绕回）。必须用
last[]作比较键。 - $n=0$ 时
scanf("%s")读空：输入里没字符串，缓冲区是垃圾值。用逐字符读到EOF并过滤非a-z，天然兼容空串。 - 顺手一条：
#define mod 1e9+7里的1e9是 double，改成const int MOD = 1000000007;。
测试点分档与考点
- $n\le5,m\le5,k\le5$：手推/暴力即可（对应 1–6 点）
- $m=0$ 或 $n=0$：只考「计数 DP」或只考「纯贪心」（7–10 点）
- $k=1$：没得选，考「同一字母重复时的增量」$f[i]=1$（11,15,19 点）
- $n,m\ge 2\times10^4$ 起：真正卡 $O(n\log n)$/大常数实现，且必然发生取模绕回（12–20 点）
题面表格写 $n,m\le 10^5$，题解写 $0\le n,m\le 10^6$ —— 造数据按大的来更保险。
一句话记住这道题
加字符 = 把口袋复印并贴尾巴；贴出来重复的，恰好是「上次用这个字母之前的口袋」那批 $G[c]$ 条，于是 $P\to 2P-G[c]$；永远挑 $G$ 最小（最久未用）的字母去追加。
DP 负责「数」，贪心负责「造」，两者共用同一组 $\{P,\,G[\cdot]\}$ 变量；算数用模值，比大小用精确值。
DP 负责「数」，贪心负责「造」，两者共用同一组 $\{P,\,G[\cdot]\}$ 变量；算数用模值，比大小用精确值。