Suppose we did `f[0]`

of the first operation, `f[1]`

of the second, `f[2]`

of the third, and `f[3]`

of the fourth, where `sum(f) == m`

.

First, all these operations commute: doing operation A followed by operation B yields the same result as doing operation B followed by operation A. Also, doing operation A followed by operation A again is the same as doing nothing. So really, we only needed to know the residues `cand[i] = f[i] % 2`

. There are only 16 different possibilities for the residues in total, so we can try them all.

We'll loop `cand`

through all 16 possibilities `(0, 0, 0, 0), (0, 0, 0, 1), ..., (1, 1, 1, 1)`

. A necessary and sufficient condition for `cand`

to be valid is that `sum(cand) % 2 == m % 2 and sum(cand) <= m`

, as only when these conditions are satisfied can we find some `f`

with `sum(f) == m`

and `cand[i] = f[i] % 2`

.

Also, as the sequence of lights definitely repeats every 6 lights, we could replace `n`

with `min(n, 6)`

. Actually, we could replace it with `min(n, 3)`

, as those lights are representative: that is, knowing the first 3 lights is enough to reconstruct what the next 3 lights will be. If the first 3 lights are X, Y, Z, then with a little effort we can prove the next 3 lights will be (X^Y^Z), Z, Y.

```
def flipLights(self, n, m):
seen = set()
for cand in itertools.product((0, 1), repeat = 4):
if sum(cand) % 2 == m % 2 and sum(cand) <= m:
A = []
for i in xrange(min(n, 3)):
light = 1
light ^= cand[0]
light ^= cand[1] and i % 2
light ^= cand[2] and i % 2 == 0
light ^= cand[3] and i % 3 == 0
A.append(light)
seen.add(tuple(A))
return len(seen)
```