def solve(self, cipher):
        """
        f[i][j] represents the number of combinations for size i*j, not necessarily solid
        f[i][j] = f[1][j]**i
        s[i][j] represents the number of combinations for size i*j, solid

        s[h][w]  = f(h,w) - sum(f[h][w-i]*s[h][i])

        be careful with TLE
        :param cipher:
        :return:
        """
        N, M = cipher
        f = [[0 for _ in xrange(M + 1)] for _ in xrange(N + 1)]
        s = [[0 for _ in xrange(M + 1)] for _ in xrange(N + 1)]

        f[1][0] = 1
        for j in xrange(1, M + 1):
            for l in self.lens:
                if j - l >= 0:
                    f[1][j] += f[1][j - l]
                    f[1][j] %= MOD

        for i in xrange(2, N + 1):
            for j in xrange(1, M + 1):
                f[i][j] = f[i - 1][j] * f[1][j]
                f[i][j] %= MOD

        for i in xrange(1, N + 1):
            for j in xrange(1, M + 1):
                s[i][j] = f[i][j]
                if s[i][j] <= 0: break
                for k in xrange(1, j):  # sum
                    s[i][j] -= f[i][j - k] * s[i][k]
                    s[i][j] %= MOD
        return s[N][M]
dataset/ETHPy150Open algorhythms/HackerRankAlgorithms/Lego Blocks.py/Solution_TLE.solve/original