4373: D. 鲁的串串 (string.c/cpp/pas)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
### 题目背景
在遥远的银河系中，宇宙大帝 Luke 正在研究一种神秘的古老语言。这个语言由 $k$ 个神秘的符文组成（即前 $k$ 个小写字母），每个符文对应一种宇宙中的基本元素。Luke 发现了一个长度为 $n$ 的古老字符序列，这个序列中所有的符文都来自这 $k$ 个基本符文。为了进一步揭示这段语言的奥秘，Luke 决定在这个字符序列的基础上，添加更多的符文来扩展它。
Luke 可以在现有的字符序列后再添加 $m$ 个符文，使得新的字符序列包含尽可能多的不同子序列。唯一的限制是，Luke 只能使用那 $k$ 个基本符文（即前 $k$ 个小写字母）来进行添加。
现在，Luke 想知道，在他添加这些符文之后，长度为 $n+m$ 的新字符序列最多可以包含多少个不同的子序列。由于答案可能非常庞大，请将结果对 $10^9 + 7$ 取模。
你的任务是帮助宇宙大帝 Luke 计算这个最大可能的子序列数量，帮助他破解古老语言的奥秘。
输入
### 输入格式
输入第一行两个数 $m$，$k$。
接下来一行一个字符串，长度为 $n$，表示原始的字符串。
输出
### 输出格式
一个数，表示答案。
样例输入 复制
1 3
ac样例输出 复制
8提示
### Examples
#### 【样例 1 输入】
```input
1 3
ac
```
#### 【样例 1 输出】
```output
8
```
#### 【样例 2,3,4 输入】
见下发文件。
#### 【样例 2,3,4 输出】
见下发文件。
### Notes
| 测试点 | $n \leq $ | $m\leq $ | $k \leq $ |
| :---------: | :----------------: | :------------------: | :---------: |
| $1$ | $1$ | $1$ | $1$ |
| $2\sim 3$ | $5$ | $0$ | $5$ |
| $4\sim 5$ | $0$ | $5$ | $5$ |
| $6$ | $5$ | $5$ | $5$ |
| $7\sim 8$ | $1000$ | $0$ | $26$ |
| $9 \sim 10$ | $0$ | $1000$ | $26$ |
| $11$ | $1000$ | $1000$ | $1$ |
| $12$ | $1000$ | $1000$ | $26$ |
| $13$ | $20000$ | $0$ | $26$ |
| $14$ | $0$ | $20000$ | $26$ |
| $15$ | $20000$ | $20000$ | $1$ |
| $16$ | $20000$ | $20000$ | $26$ |
| $17$ | $100000$ | $0$ | $26$ |
| $18$ | $0$ | $100000$ | $26$ |
| $19$ | $100000$ | $100000$ | $1$ |
| $20$ | $100000$ | $100000$ | $26$ |