# Leetcode 672

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        if n == 1:
            return 1 if presses == 0 else 2
        if n == 2:
            if presses == 0:
                return 1
            elif presses == 1:
                return 3
            else:
                return 4
        
        start = 0
        mask = [0] * 4
        if n == 3:
            start = 7
            mask[0] = 7 # 111
            mask[1] = 5 # 101
            mask[2] = 2 # 010
            mask[3] = 1 # 001
        elif n == 4:
            start = 15 # 1111
            mask[0] = 15 # 1111
            mask[1] = 5 # 0101
            mask[2] = 10 # 1010
            mask[3] = 9 # 1001
        elif n == 5:
            start = 31 # 11111
            mask[0] = 31 # 11111
            mask[1] = 21 # 10101
            mask[2] = 10 # 01010
            mask[3] = 9 # 01001
        else:
            start = 63 # 111111
            mask[0] = 63 # 111111
            mask[1] = 21 # 010101
            mask[2] = 42 # 101010
            mask[3] = 9 # 001001
        
        state = []
        for i in range(presses + 1):
            state.append([False] * (start + 1))
        self.search(state, mask, start, presses, 0)
        ans = 0
        for i in range(start + 1):
            ans += state[presses][i]
        return ans
    
    def search(self, state, mask, cur, presses, count):
        if count == presses + 1:
            return
        if state[count][cur]:
            return
        state[count][cur] = True
        for m in mask:
            self.search(state, mask, cur ^ m, presses, count + 1)