class Solution(object):
    def prisonAfterNDays(self, cells, N):
        """
        :type cells: List[int]
        :type N: int
        :rtype: List[int]
        """
        temp, k, mSet, arrs = cells[::], len(cells), set(), []

        while N:
            for i in xrange(1, k - 1):
                temp[i] = 0 if cells[i - 1] ^ cells[i + 1] else 1

            temp[0] = 0
            temp[-1] = 0
            N -= 1
            cells = temp[::]
            arrs.append(cells)
            s = ''.join(str(cells))
            if s not in mSet:
                mSet.add(s)
            else:
                break

        if N == 0:
            return cells
        n = len(mSet)
        return arrs[N % n]


if __name__ == '__main__':
    print Solution().prisonAfterNDays([0, 1, 0, 1, 1, 0, 0, 1], 7)
    # print Solution().prisonAfterNDays([0,1,0,1,1,0,0,1], 65)
    print Solution().prisonAfterNDays([1, 0, 0, 1, 0, 0, 1, 0], 1000000000)
