Squished status

#!/usr/bin/env python
import sys

def time_function(func):
    def wrapped_func(*args, **kwargs):
        from time import time
        start = time()
        sys.stderr.write('Function %s started\n' % (func.__name__,))
        res = func(*args, **kwargs)
        sys.stderr.write('Function %s finished in %.6fs\n' % (func.__name__, time() - start))
        return res
    return wrapped_func

class Problem(object):
    def __init__(self, data):
        self.max_len, self.message = data
        self.max_len = int(self.max_len)
        self.cache = {}

    def get_solution(self, msg = None):
        if msg is None:
            msg = self.message
        if msg == '':
            return 1
        if msg[0] == '0':
            return 0
        if len(msg) == 1:
            if int(msg) < self.max_len:
                return 1
            return 0
        if msg in self.cache:
            return self.cache[msg]
        result = 0
        for i in range(1, 1 + len(str(self.max_len))):
            ch = msg[:i]
            if len(ch) < i:
                break
            if int(ch) <= self.max_len:
                result += self.get_solution(msg[i:])
            else:
                break
        self.cache[msg] = result
        return result % 4207849484

@time_function
def main():
    input_file = open('input.txt')
    data = input_file.read().split()
    n = int(data.pop(0))
    for i in range(1, n + 1):
        args = data.pop(0), data.pop(0)
        result = Problem(args).get_solution()
        print "Case #%d: %s" % (i, result)

if __name__ == '__main__':
    from doctest import testmod
    print >> sys.stderr, testmod()
    main()