CF645E Intellectual Inquiry

由于不认识字母表，Bessie 被辞退了记者的工作，决定到 Fillet and Eggs Eater 学院去上学。学习了一段时间后，她现在已经认识了前 $k$ 个英文字母。 每天早晨，Bessie 都要沿着一条由 $m+n$ 块地砖组成的人行道行走上学。为了帮助 Bessie 复习，Mr. Moozing 已经用前 $k$ 个小写英文字母中的一个给前 $m$ 块地砖标上了字母，组成了一个字符串 $t$。Mr. Moozing 对 Bessie 的农场动物知识印象深刻，计划让她自己为剩下的 $n$ 块地砖标上字母。 考虑最终得到的字符串 $s$（$|s|=m+n$），表示从家到学校沿顺序标记的所有地砖所组成的字符串。对于任意索引序列 $p_{1}

输入的第一行包含两个整数 $n$ 和 $k$（$0\leq n\leq 1000000$，$1\leq k\leq 26$）。 第二行包含一个字符串 $t$（$|t|=m$，$1\leq m\leq 1000000$），字符串只包含前 $k$ 个小写英文字母。

输出 Bessie 能够通过标记最后 $n$ 块地砖所能得到的不同子序列的最大数量。由于答案可能很大，输出对 $10^{9}+7$ 取模的结果。 请注意，你并不需要使得余数本身最大化！目标是让原始值最大，然后输出其余数即可。

在第一个样例中，最大有 $8$ 种不同的子序列：""（空串）、"a"、"c"、"b"、"ac"、"ab"、"cb" 和 "acb"。 在第二个样例中，整个地砖已经完全标记。总共有 $10$ 种不同的子序列：""（空串）、"a"、"b"、"aa"、"ab"、"ba"、"aaa"、"aab"、"aba" 和 "aaba"。注意某些字符串（例如 "aa"）可以通过多种不同顺序得到，但只计作一种。 由 ChatGPT 5 翻译