TopCoder SRM 591: StringPath

public class StringPath {
    const int mod =  1000000009;
    int n, m;
    string A, B;
    int?[,,] memo;

    int newState(int row, int col, String s, char c, int bit) {
        if (((1 << col) & bit) != 0) {
            bit ^= (1 << col);
            if (s[row + col] == c) {
                if (col + 1 < m) {
                    bit |= (1 << (col + 1));
                }
                if (row + 1 < n) {
                    bit |= (1 << col);
                }
            }
        }
        return bit;
    }

    int solve(int pos, int a, int b) {
        int row = pos / m;
        int col = pos % m;
        if (row == n - 1 && col == m - 1) {
            if ((a >> col) != 0 && (b >> col) != 0) return 1;
            return 0;
        }
        if (!memo[pos, a, b].HasValue) {
            int val = 0;
            foreach (char c in Enumerable.Range('A',26)) {
                int na = newState(row, col, A, c, a);
                int nb = newState(row, col, B, c, b);
                val += solve(pos + 1, na, nb);
                val %= mod;
            }
            memo[pos, a, b] = val;
        }

        return memo[pos, a, b].Value;
    }

    public int countBoards(int n, int m, string A, string B) {
        if (A.First() != B.First()) return 0;
        if (A.Last() != B.Last()) return 0;
        this.n = n;
        this.m = m;
        this.A = A;
        this.B = B;
        memo = new int?[8 * 8, 1 << 8, 1 << 8];
        return solve(0, 1, 1);
    }
}