TopCoder SRM601: WinterAndSnowmen

public class WinterAndSnowmen {
    const int mod = 1000000007;

    static public void Add(ref int x, int value) {
        x += value;
        x %= mod;
    }

    public int getNumber(int N, int M) {
        const int BitNum = 12;
        int ans = 0;
        for (int diffBitPosition = 0; diffBitPosition < 12; diffBitPosition++) {
            int UpperBitNum = BitNum - (diffBitPosition + 1);
            var dp = new int[1 << UpperBitNum, 2, 2];
            dp[0, 0, 0] = 1;
            for (int i = 1; i <= Math.Max(N, M); i++) {
                var next = new int[1 << UpperBitNum, 2, 2];
                var upperBit = i >> (diffBitPosition + 1);
                var bit = (i & (1 << diffBitPosition)) != 0 ? 1 : 0;

                for (int j = 0; j < (1 << UpperBitNum); j++) {
                    for (int nb = 0; nb < 2; nb++) {
                        for (int mb = 0; mb < 2; mb++) {
                            if (i <= N) Add(ref next[j ^ upperBit, (nb + bit) & 1, mb], dp[j, nb, mb]);
                            if (i <= M) Add(ref next[j ^ upperBit, nb, (mb + bit) & 1], dp[j, nb, mb]);
                            Add(ref next[j, nb, mb], dp[j, nb, mb]);
                        }
                    }
                }
                dp = next;
            }

            ans += dp[0, 0, 1];
            ans %= mod;
        }

        return ans;
    }
}