Cod sursă (job #733466)

#include <stdio.h>

const char inputUrl[] = "director.in";
const char outputUrl[] = "director.out";

const int MAX = 1e4 + 1;
const int MOD = 1e9 + 7;

int w[2][MAX];
int S[2][MAX];
int poz[255];
char s[MAX];
int n, k;
int ans;

void norm(int& X) {
	if(X < 0)
		X += MOD;
	else if(X > MOD)
		X -= MOD;
}

void solve() {
	bool id = 0;
	for(int i = 1; i <= n; i++) {
		w[1][i] = 1;
		S[1][i] = S[1][i - 1] - w[1][poz[s[i]]] + w[1][i];
		norm(S[1][i]);
		poz[s[i]] = i;
	}

	for(int i = 1; i < k; i++) {
		for(int i = 'a'; i <= 'z'; i++)
			poz[i] = 0;

		for(int i = 1; i <= n; i++) {
			w[id][i] = S[id ^ 1][i - 1];
			S[id][i] = S[id][i - 1] - w[id][poz[s[i]]] + w[id][i];
			norm(S[id][i]);
			poz[s[i]] = i;
		}
		id ^= 1;
	}

	ans = S[id ^ 1][n];
}

void readInput() {
	FILE *fin = fopen(inputUrl, "r");

	fscanf(fin, "%d %d\n", &n, &k);
	fscanf(fin, "%s", (s + 1));

	fclose(fin);
}

void printAns() {
	FILE *fout = fopen(outputUrl, "w");

	fprintf(fout, "%d\n", ans);

	fclose(fout);
}

signed main()
{
	readInput();
	solve();
	printAns();
	return 0;
}