6300: 【回溯】百度2021秋招-子序列中的k种字母

金币值:1 时间限制:4.000 s 内存限制:128 M
正确:18 提交:35 正确率:51.43% 命题人:

题目描述

在数学中,某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列,如对于字符串"abc","ab" 和 "ac" 都是其子序列,而"cb"和"ca"不是。 

牛牛有一个长度为n的仅由小写字母组成的字符串s,牛牛想知道s有多少子序列恰好包含k种字母?

输入格式

第一行输入两个正整数n和k。 

第二行输入一个长度为n的仅包含小写字母的字符串s。(1 ≤ n < 10^5, 1 ≤ k ≤ 26)

输出格式

由于答案可能会很大,因此你只需要输出子序列个数对10^9+7取模的结果即可。

输入样例    复制

6 5
eecbad

输出样例    复制

3