Covers

Your task is to count the number of ways that an n \times m rectangle can be covered using at most k rectangles. In all rectangles the side lengths are integers.

For example, a 2 \times 3 rectangle can be covered in 13 ways using at most 3 rectangles:

You may assume that n and m are in the range 1 \dots 4 and k is in the range 1 \dots nm.

In a file cover.py, implement a function count that returns the number of ways to cover the rectangle.

def count(n, m, k):
    # TODO

if __name__ == "__main__":
    print(count(2,2,4)) # 8
    print(count(2,3,3)) # 13
    print(count(4,4,1)) # 1
    print(count(4,3,10)) # 3146
    print(count(4,4,16)) # 70878