DP

经典的dp问题，利用序列自动机进行处理。
每次转移都是根据当前位置向后推导，即可。

状态表示：以s[i]结尾同时长度为j的子序列的方案数。
每次转移的时候，为了做到不重不漏，借助序列自动机来更新下一个位置。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll ;
const ll mod = 1e9 + 7 ;
const int N = 1e3 + 10;
ll f[N][N] ;
char s[N];
int Next[N][30] , n , k ;
int main()
{
    scanf("%d%d",&n,&k);    
    scanf("%s",s+1);

    //初始化
    for( int i = 1 ; i <= 26 ; i++ )
        Next[n][i] = n + 1 ;

    //创建序列自动机 , Next[i]['a'] -> 第 i 个位置 下一个'a' 的位置
    for( int i = n ; i >= 1 ; i -- ){
        for( int j = 0 ; j < 26 ; j ++ )
            Next[i-1][j] = Next[i][j] ;
        Next[i-1][s[i]-'a'] = i ;
    }
    //printf("%d %d %d\n",Next[0][0],Next[0][1],Next[0][2]);
    f[0][0] = 1 ;
    for( int i = 0 ; i <= n ; i++ ){
        for( int j = 0 ; j <= min( k , i ) ; j ++ ){
            for( int c = 0 ; c < 26 ; c ++ ){
                f[Next[i][c]][j+1] = ( f[i][j] + f[Next[i][c]][j+1] ) % mod ;
            }
        }
    }
    ll ans = 0 ;
    for( int i = k ; i <= n ; i++ ){
        ans = ( ans + f[i][k] ) % mod ;
    }
    printf("%lld\n",ans);
    return 0;
}