Solution to Google Code Jam 2008 round 1C problem B

This is my solution to Google Code Jam 2008 round 1C problem B (Ugly Numbers). I think it's very elegant. However, I wonder if it's too concise. What could I improve here?

The problem:


Once upon a time in a strange situation, people called a number ugly
if it was divisible by any of the one-digit primes (2, 3, 5 or 7).
Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note
that 0 is ugly. Also note that negative numbers can also be ugly; -14
and -39 are examples of such numbers.


One day on your free time, you are gazing at a string of digits,
something like:


123456


You are amused by how many possibilities there are if you are allowed
to insert plus or minus signs between the digits. For example you can
make


1 + 234 - 5 + 6 = 236


which is ugly. Or


123 + 4 - 56 = 71


which is not ugly.


It is easy to count the number of different ways you can play with the
digits: Between each two adjacent digits you may choose put a plus
sign, a minus sign, or nothing. Therefore, if you start with D digits
there are 3^D-1 expressions you can make.


Note that it is fine to have leading zeros for a number. If the string
is "01023", then "01023", "0+1-02+3" and "01-023" are legal
expressions.


Your task is simple: Among the 3^D-1 expressions, count how many of
them evaluate to an ugly number.


Input


The first line of the input file contains the number of cases, N. Each
test case will be a single line containing a non-empty string of
decimal digits.


Output


For each test case, you should output a line


Case #X: Y


where X is the case number, starting from 1, and Y is the number of
expressions that evaluate to an ugly number.

Code:

```
from functools import lru_cache

M = 235*7
uglies = list(filter(lambda n: (int(n)%2 == 0 or
int(n)%3 == 0 or
int(n)%5 == 0 or

M = 2*3*5*7
uglies = list(filter(lambda n: (int(n)%2 == 0 or
                                int(n)%3 == 0 or
                                int(n)%5 == 0 or
                                int(n)%7 == 0),
                     range(M)))

Why the int(...) calls? Surely range returns integers?

@lru_cache(maxsize=None)
def f(line, k=None):
    if k == None:
        return sum([f(line, k) for k in uglies])

I'm not really a Python programmer so I'm not sure how Pythonic it is, but to me this overloading is a code smell. I would prefer to split out one function which takes just the line and another which does the real work.

Also, what is k? I managed to figure it out by reverse engineering, but a short comment would have helped a lot.

return sum([
        (1 if (int(line) % M) == k else 0),

        sum([f(line[:p],
               (k-int(line[p:])) % M)
             for p in range(1, len(line))]),

        sum([f(line[:p],
               (k+int(line[p:])) % M)
             for p in range(1, len(line))]),
        ])

Again, it would be nice to have a short comment explaining why the recursion works on suffixes (and proving that it's correct, which isn't obvious, because it would seem to allow inserting a - before the first digit of the line in contradiction to the spec).

It would also be nice to see a justification for working on string slices rather than using integers with div/mod by powers of 10.

StackExchange Code Review Q#158971, answer score: 5