Cod sursă (job #733464)

#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 solve() {
	bool id = 0;
	for(int i = 1; i <= n; i++) {
		w[1][i] = 1;
		S[1][i] = (MOD + S[1][i - 1] + w[1][i] - w[1][poz[s[i]]]) % MOD;
		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] = (MOD + S[id][i - 1] + w[id][i] - w[id][poz[s[i]]] ) % MOD;
			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);
}

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