Cod sursă (job #733028)

///dp(j) -> din primele i caractere cu lungimea j care se termina in caracterul s[i]
///sum[j] suma tuturor caracterelor de lungime j distincte
///last[ch][j]

#include <fstream>
#include <string>

using namespace std;

ifstream cin ("director.in");
ofstream cout ("director.out");

const int MOD = 1e9 + 7;
const int N = 1e4;
int dp[N + 1], last[40][N + 1], sum[N + 1];

int n, k;

string s;

int main()
{
    cin >> n >> k >> s;
    s = '@' + s;
    for (int i = 0; i < 26; ++i)
        for (int j = 1; j <= k; ++j)
            last[i][j] = -1;
    for (int i = 1; i < s.size(); ++i)
    {
        int ch = s[i] - 'a';
        dp[1] = 1;
        for (int j = 2; j <= k; ++j)
            dp[j] = sum[j - 1];
        for (int j = 1; j <= k; ++j)
        {
            sum[j] = (sum[j] + dp[j]) % MOD;
            if (last[ch][j] != -1)
                sum[j] = (sum[j] - last[ch][j] + MOD) % MOD;
            last[ch][j] = dp[j];
        }
    }
    cout << sum[k] << '\n';
    return 0;
}