操作集锦

题号：NC204019
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一款自走棋有26种操作,每种操作我们都用 $a,b,c,d,...,x,y,z$ 的符号来代替.

现在牛牛有一个长度为 $n$ 的操作序列,他现在可以从里面拿出某些操作来组合成一个操作视频, 比如说操作序列是 $abcd$ ,那么操作视频就有 $a,b,c,d,ab,ac,ad$ 等(也就是操作序列的子序列).他现在想知道长度为 $k$ 且本质不同的操作视频有多少种.

比如对于 $abab$ ，长度为 $2$ 且本质不同的结果有 $ab,aa,ba,bb$ 。

考虑到答案可能非常大,你只需要输出在模 $1e9+7$ 意义下的答案就可以了.

第一行两个整数.
第二行一个长度为的字符串,保证只存在小写字母.

一行一个整数表示长度为且本质不同的操作视频的个数.

示例1

复制

3 1
abc

复制