CF645E.Intellectual Inquiry

After getting kicked out of her reporting job for not knowing the alphabet, Bessie has decided to attend school at the Fillet and Eggs Eater Academy. She has been making good progress with her studies and now knows the first k English letters.

Each morning, Bessie travels to school along a sidewalk consisting of m + n tiles. In order to help Bessie review, Mr. Moozing has labeled each of the first m sidewalk tiles with one of the first k lowercase English letters, spelling out a string t. Mr. Moozing, impressed by Bessie's extensive knowledge of farm animals, plans to let her finish labeling the last n tiles of the sidewalk by herself.

Consider the resulting string s (|s| = m + n) consisting of letters labeled on tiles in order from home to school. For any sequence of indices _p_1 < _p_2 < ... < p__q we can define subsequence of the string s as string _s__p_1_s__p_2... s__p__q. Two subsequences are considered to be distinct if they differ as strings. Bessie wants to label the remaining part of the sidewalk such that the number of distinct subsequences of tiles is maximum possible. However, since Bessie hasn't even finished learning the alphabet, she needs your help!

Note that empty subsequence also counts.

在因不认识英文字母表而被解雇了记者工作后，贝茜决定去“鱼排与鸡蛋食客学院”上学。她学习进展顺利，目前已掌握了前 $k$ 个英文字母。

每天早晨，贝茜沿着一条由 $m+n$ 块地砖铺成的人行道步行去学校。为了帮助贝茜复习，穆辛老师已在前 $m$ 块地砖上，用前 $k$ 个小写英文字母之一标出了一个字符串 $t$。穆辛老师对贝茜广博的家畜知识印象深刻，因此打算让她自己完成剩余 $n$ 块地砖的标注工作。

考虑最终得到的字符串 $s$（其长度 $|s| = m + n$），它由从家到学校的地砖上所标的字母按顺序拼接而成。对于任意一组严格递增的下标序列 $p_1 < p_2 < \dots < p_q$，可将字符串 $s$ 的一个子序列定义为字符串 $s_{p_1}s_{p_2}\dots s_{p_q}$。若两个子序列作为字符串不同，则认为它们是不同的子序列。贝茜希望以某种方式标注剩余的地砖，使得整个字符串 $s$ 的不同子序列总数达到最大可能值。然而，由于贝茜甚至还没学完全部字母表，她需要你的帮助！

注意：空子序列也计入总数。

The first line of the input contains two integers n and k (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 26).

The second line contains a string t (|t| = m, 1 ≤ m ≤ 1 000 000) consisting of only first k lowercase English letters.

输入的第一行包含两个整数 $n$ 和 $k$（$0 ≤ n ≤ 1 000 000$，$1 ≤ k ≤ 26$）。

第二行包含一个字符串 $t$（$|t| = m$，$1 ≤ m ≤ 1 000 000$），该字符串仅由前 $k$ 个小写英文字母组成。

Determine the maximum number of distinct subsequences Bessie can form after labeling the last n sidewalk tiles each with one of the first k lowercase English letters. Since this number can be rather large, you should print it modulo 109 + 7.

Please note, that you are not asked to maximize the remainder modulo 109 + 7! The goal is to maximize the initial value and then print the remainder.

确定贝茜在将最后 $n$ 块人行道地砖各自标上前 $k$ 个小写英文字母之一后，所能形成的不同子序列的最大数量。由于该数值可能非常大，你应输出其对 $10^9 + 7$ 取模的结果。

请注意，你并非要求最大化对 $10^9 + 7$ 取模后的余数！目标是先最大化原始数值，再输出该最大值对 $10^9 + 7$ 的余数。

In the first sample, the optimal labeling gives 8 different subsequences: "" (the empty string), "a", "c", "b", "ac", "ab", "cb", and "acb".

In the second sample, the entire sidewalk is already labeled. The are 10 possible different subsequences: "" (the empty string), "a", "b", "aa", "ab", "ba", "aaa", "aab", "aba", and "aaba". Note that some strings, including "aa", can be obtained with multiple sequences of tiles, but are only counted once.

在第一个样例中，最优的标记方案产生了 8 个不同的子序列：""（空字符串）、"a"、"c"、"b"、"ac"、"ab"、"cb" 和 "acb"。

在第二个样例中，整条人行道已被完全标记。共有 10 个可能的不同子序列：""（空字符串）、"a"、"b"、"aa"、"ab"、"ba"、"aaa"、"aab"、"aba" 和 "aaba"。注意，某些字符串（包括 "aa"）可通过多组地砖序列得到，但仅计数一次。