Cod sursă (job #733177)

#include <fstream>
#include <string>

using namespace std;

const int Nmax = 10005;
const int SIGMA = 26;
const int MOD = 1000000007;

long long dp[2][Nmax], frecv[SIGMA];

int main(){
    ifstream fin("director.in");
    ofstream fout("director.out");

    int n, k;
    long long sum;
    char c;
    string s;
    bool val;

    fin >> n >> k;
    fin >> s;

    for(unsigned int i = 0; i < s.size(); i++){
        dp[0][i] = 1;
    }

    for(int j = 1; j < k; j++){
        sum = 0;
        val = j & 1;

        for(int i = s.size() - 1; i >= 0; i--){
            c = s[i];

            dp[val][i] = sum;
            sum = sum + dp[!val][i] - frecv[c - 'a'];
            sum = sum % MOD;
            frecv[c - 'a'] = dp[!val][i];
        }

        for(int i = 0; i < SIGMA; i++){
            frecv[i] = 0;
        }
    }

    val = !(k & 1);
    for(int i = s.size() - 1; i >= 0; i--){
        c = s[i];
        frecv[c - 'a'] = dp[val][i];
    }

    sum = 0;
    for(int i = 0; i < SIGMA; i++){
        sum += frecv[i];
    }
    sum = sum % MOD;

    fout << sum;

    return 0;
}