output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 \ldots A_{N}
attempt: from collections import defaultdict
  
  N = int(input())
  A = [int(x) for x in input().split()]
  p = 10**9 + 7
  B = [[0 for j in range(20)] for i in range(N + 1)]
  D = defaultdict(list)
  D[0].append(0)
  for i in range(N):
      a = A[i]
      b = 0
      for j in range(20):
          B[i + 1][j] = B[i][j]
          B[i + 1][j] += a % 2
          B[i + 1][j] %= 2
          b += B[i + 1][j] * 2**j
          a //= 2
      D[b].append(i + 1)
  cnt = 0
  
  
  def zig(A, Z):
      As, Ar, Zs, Zr = 0, 0, 0, 0
      i, j = len(A) - 1, len(Z) - 1
      if A[-1] > Z[-1]:
          while A[i] > Z[-1]:
              i -= 1
          Zr = 1
      else:
          while Z[j] > A[-1]:
              j -= 1
          Ar = 1
      while i > 0 and j > 0:
          if Ar:
              j -= 1
              while A[i] > Z[j]:
                  As + -Ar
                  i -= 1
                  if i == 0:
                      break
              Zr = As % p
              As, Ar = 0, 0
          else:
              i -= 1
              while Z[j] > A[i]:
                  Zs += Zr
                  j -= 1
                  if j == 0:
                      break
              Ar = Zs % p
              Zs = 0
      return Zr
  
  
  if b != 0:
      cnt += zig(D[b], D[0])
  else:
      for k in D.keys():
          if k:
              cnt += zig(D[k], D[0]) + 1
          else:
              cnt += 2 ** (len(D[0]) - 2) % p
  print(cnt % p)
  
problem_description: Statement
  
  The _beauty_ of a sequence a of length n is defined as a_1 \oplus \cdots
  \oplus a_n, where \oplus denotes the bitwise exclusive or (XOR).
  
  You are given a sequence A of length N. Snuke will insert zero or more
  partitions in A to divide it into some number of non-empty contiguous
  subsequences.
  
  There are 2^{N-1} possible ways to insert partitions. How many of them divide
  A into sequences whose beauties are all equal? Find this count modulo
  10^{9}+7.
samples: [{"input": "3\n    1 2 3", "output": "3\n    \n\nFour ways of dividing A shown below satisfy the condition. The condition is\nnot satisfied only if A is divided into (1),(2),(3).\n\n  * (1,2,3)\n  * (1),(2,3)\n  * (1,2),(3)\n\n* * *"}, {"input": "3\n    1 2 2", "output": "1\n    \n\n* * *"}, {"input": "32\n    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "output": "147483634\n    \n\nFind the count modulo 10^{9}+7.\n\n* * *"}, {"input": "24\n    1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2", "output": "292"}]