Intellectual Inquiry

现在有一个n+m位的字符串（仅由前k个小写字母组成），前m位已经填好，需要你去填剩下的n位，使得最后的串的不同的子序列数量尽量多。 两个子序列被认为不同，当且仅当它们组成的字符串不相同。 输出最多的不同子序列数量mod 1e9+7的值。 Translated by @vanilla

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_{p1}s_{p2}...\ s_{pq} $ . 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.

The first line of the input contains two integers $ n $ and $ k $ ( $ 0<=n<=1000000 $ , $ 1<=k<=26 $ ). The second line contains a string $ t $ ( $ |t|=m,1<=m<=1000000 $ ) consisting of only first $ k $ lowercase English letters.

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 $ 10^{9}+7 $ . Please note, that you are not asked to maximize the remainder modulo $ 10^{9}+7 $ ! The goal is to maximize the initial value and then print the remainder.

1 3
ac

8

0 2
aaba

10

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.