题目描述

在遥远的银河系中，宇宙大帝 Luke 正在研究一种神秘的古老语言。这个语言由 $k$ 个神秘的符文组成（即前 $k$ 个小写字母），每个符文对应一种宇宙中的基本元素。Luke 发现了一个长度为 $n$ 的古老字符序列，这个序列中所有的符文都来自这 $k$ 个基本符文。为了进一步揭示这段语言的奥秘，Luke 决定在这个字符序列的基础上，添加更多的符文来扩展它。

Luke 可以在现有的字符序列后再添加 $m$ 个符文，使得新的字符序列包含尽可能多的不同子序列。唯一的限制是，Luke 只能使用那 $k$ 个基本符文（即前 $k$ 个小写字母）来进行添加。

现在，Luke 想知道，在他添加这些符文之后，长度为 $n+m$ 的新字符序列最多可以包含多少个不同的子序列。由于答案可能非常庞大，请将结果对 $10^9 + 7$ 取模。

你的任务是帮助宇宙大帝 Luke 计算这个最大可能的子序列数量，帮助他破解古老语言的奥秘。输入第一行两个数 $m$，$k$。

接下来一行一个字符串，长度为 $n$，表示原始的字符串。

输入格式

输入第一行两个数 $m$，$k$。

接下来一行一个字符串，长度为 $n$，表示原始的字符串。

输出格式

一个数，表示答案。

样例输入 #1

1 3
ac

样例输出 #1

8

数据范围