Hackerrank Lego Blocks solution. Permute all solid walls.

legos.py

import sys
from random import choice
mod = 1000000007
import math
import marshal

cache = {}

def memoized(f): 
    """Memoize any function."""

    def decorated(*args):
        key = (f, marshal.dumps(args))
        if key in cache:
            return cache[key]

        cache[key] = f(*args)
        return cache[key]

    return decorated


@memoized
def t(width):
    if width < 0: return 0 
    if width == 0: return 1
    if width > 0: 
        out = t(width-1) + t(width-2) + t(width-3) + t(width-4)
        return out

@memoized
def all_non_solid(width,height):
    return t(width)**height

@memoized
def permute_solids(width,height):
    return all_non_solid(width,height) - sum([permute_solids(x,height) * all_non_solid(width-x,height) for x in xrange(1,width)])


if __name__ == '__main__':
    inpt = sys.stdin.readlines()
    num_cases = inpt[0]
    cases = [[int(y) for y in x.split()] for x in inpt[1:]]
    for case in cases:
        height,width = case
        print permute_solids(height,width) % mod 

This is not working