int res[kN], aux[kN], a[kN], sz;
void Rec(int t, int p, int n, int k) {
	if (t > n) {
		if (n % p == 0)
			for (int i = 1; i <= p; ++i) res[sz++] = aux[i];
	} else {
		aux[t] = aux[t - p];
		Rec(t + 1, p, n, k);
		for (aux[t] = aux[t - p] + 1; aux[t] < k; ++aux[t]) Rec(t + 1, t, n, k);
	}
}
int DeBruijn(int k, int n) {
	// return cyclic string of length k^n such that every string of length n using k character appears as a substring.
	if (k == 1) return res[0] = 0, 1;
	fill(aux, aux + k * n, 0);
	return sz = 0, Rec(1, 1, n, k), sz;
}
