There is a room with `n`

lights which are turned on initially and 4 buttons on the wall. After performing exactly `m`

unknown operations towards buttons, you need to return how many different kinds of status of the `n`

lights could be.

Suppose `n`

lights are labeled as number [1, 2, 3 …, n], function of these 4 buttons are given below:

- Flip all the lights.
- Flip lights with even numbers.
- Flip lights with odd numbers.
- Flip lights with (3k + 1) numbers, k = 0, 1, 2, …

**Example 1:**

Input:n = 1, m = 1.Output:2Explanation:Status can be: [on], [off]

**Example 2:**

Input:n = 2, m = 1.Output:3Explanation:Status can be: [on, off], [off, on], [off, off]

**Example 3:**

Input:n = 3, m = 1.Output:4Explanation:Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

**Note:** `n`

and `m`

both fit in range [0, 1000].

class Solution(object): def flipLights(self, n, m): """ :type n: int :type m: int :rtype: int """ if m==0: return 1 if n == 1: return 2 def h2(): status = [[0]*4 for _ in xrange(m+1)] status[0][3] = 1 for i in range(1,m+1): for j,s in enumerate(status[i-1]): if s: for idx in range(4): if idx != j: status[i][idx] = 1 return sum(status[m]) def h3(): status = [[0]*8 for _ in xrange(m+1)] status[0][7] = 1 for i in range(1,m+1): for j,s in enumerate(status[i-1]): if s: status[i][j^7] = 1 status[i][j^5] = 1 status[i][j^2] = 1 status[i][j^1] = 1 return sum(status[m]) if n==2: return h2() return h3()