public class Excavations2 {
long?[,] choose = new long?[55, 55];
long Choose(int s, int t) {
if (!choose[s, t].HasValue) {
if (t == 0 || t == s)
choose[s, t] = 1;
else
choose[s, t] = Choose(s - 1, t - 1) + Choose(s - 1, t);
}
return choose[s, t].Value;
}
public long count(int[] kind, int[] found, int K) {
int N = kind.Length;
var hist = new int[55];
foreach (var k in kind) hist[k]++;
var dp = new long[K + 1];
dp[0] = 1;
foreach (var f in found) {
var next = new long[K + 1];
for (int j = K - 1; j >= 0; j--) {
for (int add = 1; add <= hist[f]; add++) {
if (j + add <= K) {
next[j + add] += dp[j] * Choose(hist[f], add);
}
}
}
dp = next;
}
return dp[K];
}
}