TopCoder SRM599: SimilarNames2

public class SimilarNames2 {
    int mod = 1000000007;

    int?[,] memo;

    int dfs(string[] names, int pos, int L) {
        if (L == 0)
            return 1;
        if (!memo[pos, L].HasValue) {
            int val = 0;

            for (int i = 0; i < names.Length; i++) {
                if (i == pos) continue;
                if (names[i].StartsWith(names[pos])) {
                    val += dfs(names, i, L - 1);
                    val %= mod;
                }
            }

            memo[pos, L] = val;
        }
        return memo[pos, L].Value;
    }

    public int count(string[] names, int L) {
        int n = names.Length;
        long ans = 0;

        memo = new int?[n, L + 1];
        int free = n - L;

        for (int i = 0; i < n; i++) {
            ans += dfs(names, i, L - 1);
            ans %= mod;
        }

        for (int i = 1; i <= free; i++) {
            ans *= i;
            ans %= mod;
        }

        return (int)ans;
    }
}