Problem:
 Score : 800 points    Problem 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 .      Constraints  All values in input are integers.  1 \leq N \leq 5 \times 10^5  0 \leq A_i < 2^{20}         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \ldots  A_{N}       Output Print the answer.        Sample Input 1 3
1 2 3      Sample Output 1 3  Four ways of dividing A shown below satisfy the condition. The condition is not satisfied only if A is divided into (1),(2),(3) .   (1,2,3)  (1),(2,3)  (1,2),(3)        Sample Input 2 3
1 2 2      Sample Output 2 1       Sample Input 3 32
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      Sample Output 3 147483634  Find the count modulo 10^{9}+7 .       Sample Input 4 24
1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2      Sample Output 4 292

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
max_a = 2 ** 20
MOD = 10 ** 9 + 7

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] ^ a[i]


if ru[-1] != 0:
    
    dp = [0] * (max_a)
    dp[0] = 1
    tot_ex0 = 0
    for i in range(n):
        if i == n - 1:
            print(dp[0])
            exit()
        if ru[i + 1] == 0:
            dp[0] += tot_ex0
            dp[0] %= MOD
        elif ru[i + 1] == ru[-1]:
            dp[ru[i + 1]] += dp[0]
            dp[ru[i + 1]] %= MOD
            tot_ex0 += dp[0]
            tot_ex0 %= MOD
else:
    
    dp = [0] * max_a
    dq = [1] * max_a
    set_evaled = [0] * max_a
    times = 0
    ans = 0
    for i in range(n):
        if i == n - 1:
            ans = sum(dp)
            break
        elif ru[i + 1] == 0:
            
            
            
            times += 1
        else:
            dq[ru[i + 1]] += (times - set_evaled[ru[i + 1]]) * dp[ru[i + 1]]
            dq[ru[i + 1]] %= MOD
            set_evaled[ru[i + 1]] = times
            dp[ru[i + 1]] += dq[ru[i + 1]]
            dp[ru[i + 1]] %= MOD
    
    cnt_0 = sum([1 for i in range(n) if ru[i + 1] == 0])
    ans = (ans + pow(2, cnt_0 - 1, MOD)) % MOD
    print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

data=[0]
for i in range(N):
    data.append(data[-1]^A[i])

if data[-1]==0:
    ans=0
    zero=[int(data[i]==0) for i in range(N+1)]
    for i in range(1,N+1):
        zero[i]+=zero[i-1]

    val={}
    for i in range(N+1):
        if data[i]!=0:
            if data[i] not in val:
                val[data[i]]=[]
            val[data[i]].append(i)

    for v in val:
        B=0
        W=1
        for i in range(len(val[v])):
            j=val[v][i]
            if i!=len(val[v])-1:
                B+=W
                W+=B*(zero[val[v][i+1]]-zero[j])
                B%=mod;W%=mod
            else:
                B+=W
                B%=mod
        ans+=B
        ans%=mod

    n=data.count(0)
    ans+=pow(2,n-2,mod)
    ans%=mod
    print(ans)
else:
    val=data[-1]
    que=[0]*2**20
    dp=[0]*(N+1)
    dp[0]=1
    que[0]=1
    for i in range(1,N+1):
        j=data[i]
        dp[i]=que[j^val]
        que[data[i]]+=dp[i]
        que[data[i]]%=mod

    print(dp[N]%mod)

Solution (Python):
from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
acc = [0]
acc0 = [0]*(n+1)
for i in range(n):
  acc.append(acc[-1]^a[i])
  if i:
    acc0[i+1] += acc0[i]
  if acc[-1] == 0:
    acc0[i+1] += 1
if acc[-1] != 0:
  s = acc[-1]
  ansls = []
  cnt0 = 0
  cnts = 0
  flg = 0
  dp = [0,0]
  for i in range(1,n+1):
    if acc[i] == s:
      dp = [dp[0]+dp[1]+1,dp[1]]
    elif acc[i] == 0:
      dp = [dp[0],dp[0]+dp[1]]
    dp[0] %= mod
    dp[1] %= mod
  print((dp[1]+1)%mod)
else:
  dcn = defaultdict(list)
  dp = defaultdict(list)
  c0 = 0
  for i in range(1,n+1):
    if acc[i]:
      dcn[acc[i]].append(i)
    else:
      c0 += 1
  ans = pow(2,c0-1,mod)
  for i in range(1,n+1):
    t = acc[i]
    if t:
      if not dp[t]:
        dp[t] = [1,0]
      else:
        idx = bisect.bisect_left(dcn[t],i)
        n0 = acc0[i]-acc0[dcn[t][idx-1]]
        dp[t][1] += n0*dp[t][0]
        dp[t][0] += dp[t][1]+1
        dp[t][0] %= mod
        dp[t][1] %= mod
  for t,ls in dp.items():
    ans += ls[0]
    ans %= mod
  print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=10**9+7
    n=II()
    aa=LI()
    cs=[0]
    for a in aa:cs.append(cs[-1]^a)
    

    cnt={}
    cnt0=[1]*len(cs)
    for i,s in enumerate(cs[1:],1):
        if s==0:
            cnt0[i]=cnt0[i-1]+1
        elif s in cnt:
            cnt0[i]=cnt0[i-1]
            c0=cnt0[i]-cnt0[cnt[s][2]]
            cnt[s][0]=(cnt[s][0]+cnt[s][1]*c0)%md
            cnt[s][1]=(cnt[s][1]+cnt[s][0])%md
            cnt[s][2]=i
        else:
            cnt0[i]=cnt0[i-1]
            cnt[s]=[1,1,i]
    
    

    if cs[-1]==0:ans=sum(v[1] for v in cnt.values())+pow(2,cnt0[-1]-2,md)
    else:ans=cnt[cs[-1]][0]
    print(ans%md)

main()

Solution (Python):
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    mod = 1000000007

    for i in range(N-1):
        A[i+1] ^= A[i]
    if A[-1]:
        a = A[-1]
        ans_a = 0
        ans_zero = 1
        for i in range(N-1):
            if A[i] == a:
                ans_a = (ans_a + ans_zero)%mod
            elif A[i] == 0:
                ans_zero = (ans_zero + ans_a)%mod
        print(ans_zero)
    else:
        dic = {}
        zero_num = 0
        for a in A:
            if a:
                if a in dic:
                    dic[a].append(zero_num)
                else:
                    dic[a] = [zero_num]
            else:
                zero_num += 1
        ans = (1 << (zero_num-1))%mod
        for X in dic.values():
            ans_x = 1
            ans_zero = 1
            for i in range(1, len(X)):
                ans_zero = (ans_zero + ans_x * (X[i] - X[i-1])) % mod
                ans_x = (ans_x + ans_zero) % mod
            ans = (ans + ans_x)%mod
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

"""
Writer:SPD_9X2
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e


区分けされた部分1つ分のxorをAとすると、全体のxorは0かAかじゃないといけない
A→0→A→0となる部分に仕切りを入れられる
→DP

全体のxorが0以外の時は簡単→普通にDPすればいいだけ

全体のxorが0の時は、0を含め、出て来たすべてのxorに関して調べなきゃいけない
0が多いとき、計算量がO(N**2)になっちゃいそう…
Aをまとめて処理しなくてはいけない？

Aとしてありうるのは途中で出て来た0を含めたすべての数字
そこ1箇所で切ったのも採用可能＋今まで出て来たAのうち、それ以降で1度でも0が出たものに加えるのも可能
→0の選び方も自由だからなぁ…

愚直なdp遷移を考えてみる
dp[A] = 1 + Σdp[今まで出たA] * (その間にある0の数) →O(N**2)じゃ…(死)
どうやって高速化しよう…→上の推移式をO(1)で計算できないか？
→Σdp[今まで出たA]を記録して置けば、その間にあるAは全体で同数増加なのでO(1)で計算できる！！

"""
mod = 10**9+7
N = int(input())

a = list(map(int,input().split()))

allxor = 0
for i in range(N):
    allxor ^= a[i]

if allxor != 0: 

    dp = [1,0] 

    nxor = 0
    for i in range(N-1):
        ndp = [dp[0] % mod,dp[1] % mod]
        nxor ^= a[i]

        if nxor == 0:
            ndp[0] += dp[1]
        elif nxor == allxor:
            ndp[1] += dp[0]

        dp = ndp
        

    print (dp[0] % mod)

else:

    
    
    
    
    

    zsum = [1]
    lastA = {}
    sumdic = {}
    inddic = {}
    nxor = 0

    for i in range(N-1):

        nxor ^= a[i]

        if nxor == 0:
            zsum.append(zsum[-1] + 1)
            continue
        else:
            zsum.append(zsum[-1])

        if nxor not in inddic:
            inddic[nxor] = i
            sumdic[nxor] = 1
            lastA[nxor] = 1
        else:
            dpa = lastA[nxor] + sumdic[nxor] * (zsum[-1] - zsum[inddic[nxor]])
            lastA[nxor] = dpa % mod
            sumdic[nxor] += dpa % mod
            sumdic[nxor] %= mod
            inddic[nxor] = i

            

    ans = 0
    
    for i in sumdic:
        ans += sumdic[i]
        ans %= mod

    

    ans += pow(2,zsum[-1]-1,mod)

    print (ans % mod)

Solution (Python):
from collections import defaultdict
from bisect import bisect_left as bisect
import sys
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
S = [0]*(N+1)
zeros = []
count = defaultdict(list)
now = -1
for i in range(N):
    S[i] = S[i-1]^A[i]
    if S[i] == 0:
        zeros.append(i)
    else:
        count[S[i]].append(i)
if S[N-1] != 0:
    a = S[N-1]
    res = []
    cnt = 0
    for i in count[a]:
        res.append(bisect(zeros, i)-cnt)
        cnt+=res[-1]
    res0 = 1
    res1 = 0
    for c in res:
        res0 = res0+res1*c
        res1 = res1+res0
        res0%=mod
        res1%=mod
    print(res0)
    sys.exit()
ans = pow(2, len(zeros)-1, mod)
for a in count.keys():
    cnt = 0
    res = []
    for i in count[a]:
        res.append(bisect(zeros, i)-cnt)
        cnt+=res[-1]
    res0 = 1
    res1 = 0
    for c in res:
        res0 = res0+res1*c
        res1 = res1+res0
        res0%=mod
        res1%=mod
    ans+=res1
    ans%=mod
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

mod=10**9+7

S=[A[0]]
for i in range(1,N):
    S.append(S[-1]^A[i])

if S[-1]==0:
    sss=max(S)
    data=[[] for i in range(sss+1)]

    for i in range(N):
        data[S[i]].append(i)

    count_0=[0]*N
    for u in data[0]:
        count_0[u]+=1
    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=pow(2,len(data[0])-1,mod)

    for i in range(1,sss+1):
        if data[i]:
            h=data[i]
            l=len(h)
            dp=[1,1]
            for j in range(1,l):
                d=[0,0]
                num=count_0[h[j]]-count_0[h[j-1]]
                d[0]=(dp[0]+dp[1]*num)%mod
                d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
                dp=d
            ans=(ans+dp[1])%mod

else:
    qqq=S[-1]
    h=[]
    count_0=[0]*N
    for i in range(N):
        if S[i]==qqq:
            h.append(i)
        elif S[i]==0:
            count_0[i]=1

    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=0

    l=len(h)
    dp=[1,1]
    for j in range(1,l):
        d=[0,0]
        num=count_0[h[j]]-count_0[h[j-1]]
        d[0]=(dp[0]+dp[1]*num)%mod
        d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
        dp=d
    ans=(ans+dp[0])%mod
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

MOD = 10**9+7
N = int(readline())
A = list(map(int, readline().split()))
SA = [0]*N
SA[0] = A[0]
for i in range(1, N):
    SA[i] = SA[i-1]^A[i]
table = [int(sa == 0) for sa in SA]
for i in range(1, N):
    table[i] += table[i-1]

table.append(0)
cnt = 0
pre = [-1]*(1<<20)
dp0 = [1]*(1<<20)
dp = [0]*(1<<20)
for i in range(N):
    a = SA[i]    
    if a:
        y = table[i]-table[pre[a]]
        pre[a] = i
        dp[a], dp0[a] = dp0[a] + (1+y)*dp[a], dp0[a] + y*dp[a]
        dp[a] %= MOD
        dp0[a] %= MOD
    else:
        cnt += 1

if SA[-1]:
    ans = dp0[SA[-1]]
else:
    ans = pow(2, cnt-1, MOD)
    for t in dp:
        ans = (ans+t)%MOD
print(ans)

Solution (Python):
from itertools import accumulate
from operator import xor

MOD = 10**9 + 7
M = 2**20

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    Bs = list(accumulate([0]+As, xor))

    if Bs[-1] != 0:
        dp = [1, 0]
        for B in Bs[:-1]:
            if B == 0:
                dp[0] = (dp[0]+dp[1]) % MOD
            elif B == Bs[-1]:
                dp[1] = (dp[0]+dp[1]) % MOD
        return dp[0]
    else:
        ans = (2 ** (Bs.count(0)-2)) % MOD
        RunLens = [[] for _ in range(M)]
        num0 = 0
        num0Prevs = [0] * M
        numBs = [0] * M
        for B in Bs:
            if B == 0:
                num0 += 1
            else:
                if num0 != num0Prevs[B]:
                    RunLens[B].append(numBs[B])
                    RunLens[B].append(num0 - num0Prevs[B])
                    numBs[B] = 0
                    num0Prevs[B] = num0
                numBs[B] += 1
        for B in range(M):
            RunLens[B].append(numBs[B])
            RunLens[B].append(num0 - num0Prevs[B])

        for B in range(M):
            if len(RunLens[B]) == 2: continue
            dp = [1, 0]
            for i, RL in enumerate(RunLens[B][2:-1], 1):
                dp[i%2] = (dp[i%2] + dp[1-i%2]*RL) % MOD
            ans = (ans + dp[1]) % MOD
        return ans

print(solve())

Solution (Python):
def pow(n,k,m):
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

MOD = 10**9 + 7

n = int(input())

a = list(map(int,input().split()))

for i in range(1,n):
    a[i] = a[i]^a[i-1] 

zero = [0 for i in range(n)] 

if a[0] == 0: zero[0] = 1

for i in range(1,n):
    if a[i] == 0:zero[i] = zero[i-1]+1
    else : zero[i] = zero[i-1]

dp = [0 for i in range(n)]

pre,dpsum = {},{}

for i in range(n):
    if a[i] == 0:continue
    if pre.get(a[i]) is None:
        dp[i] = 1
        pre[a[i]] = i
        dpsum[a[i]] = 1
    else:
        j = pre[a[i]]
        z = zero[i]-zero[j]
        dp[i] = (dpsum[a[i]]*z + dp[j]) % MOD
        pre[a[i]] = i
        dpsum[a[i]] = (dp[i]+dpsum[a[i]]) % MOD

if a[-1] != 0:
    print(dp[-1])
else:
    print((pow(2,zero[-1]-1,MOD)+sum(dp)) % MOD)

Solution (Python):
MAX = 10**9 + 7
MAXAi = 1<<20

def solve2():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    xor_acu = [0] * (N + 1)
    for i in range(1, N + 1):
        xor_acu[i] = xor_acu[i - 1] ^ arr[i - 1]
    dp = [[not j for i in range(MAXAi)] for j in range(2)]
    cnt = [0 for i in range (MAXAi)]
    cnt_zero = 0
    for i in range(1, N + 1):
        if xor_acu[i] == 0:
            cnt_zero += 1
        dp[0][xor_acu[i]] += dp[1][xor_acu[i]] * (cnt_zero - cnt[xor_acu[i]])
        dp[0][xor_acu[i]] %= MAX
        dp[1][xor_acu[i]] += dp[0][xor_acu[i]]
        dp[1][xor_acu[i]] %= MAX
        cnt[xor_acu[i]] = cnt_zero
    if xor_acu[N] != 0:
        ret = dp[0][xor_acu[N]]
    else:
        ret = pow(2, cnt_zero - 1, MAX)
        for j in range(1, MAXAi):
            ret += dp[1][j]
            ret %= MAX
    print str(ret)

if __name__ == '__main__':
    solve2()

Solution (Python):





def main():
    import sys
    input = sys.stdin.readline

    mod = 10**9+7
    N = int(input())
    A = [int(i) for i in input().split()]

    
    cum_xor = [0]
    for a in A:
        cum_xor.append(cum_xor[-1] ^ a)

    if cum_xor[-1] != 0:
        dp = [[0]*2 for i in range(N+1)]
        
        
        
        X = cum_xor[-1]
        dp[0][0] = 1
        for i in range(1, N + 1):  
            dp[i][0] = dp[i - 1][0] % mod
            dp[i][1] = dp[i - 1][1] % mod
            if cum_xor[i] == 0:
                dp[i][0] += dp[i - 1][1]
            elif cum_xor[i] == X:
                dp[i][1] += dp[i-1][0]
        
        print(dp[N-1][0] % mod)
    else:
        
        dp = [[1, 0] for i in range((1 << 20) + 1)]

        
        cnt_zero_prev_cumXOR_i = [0] * ((1 << 20)+1)
        cnt_zero_now = 0

        for i in range(1, N + 1):
            if cum_xor[i] == 0:
                cnt_zero_now += 1
            else:
                
                dp[cum_xor[i]][0] += dp[cum_xor[i]][1] * \
                    (cnt_zero_now - cnt_zero_prev_cumXOR_i[cum_xor[i]])
                dp[cum_xor[i]][0] %= mod
                
                dp[cum_xor[i]][1] += dp[cum_xor[i]][0]
                dp[cum_xor[i]][1] %= mod
                
                cnt_zero_prev_cumXOR_i[cum_xor[i]] = cnt_zero_now
        ans = 0
        for c in set(cum_xor):
            ans += dp[c][1]
            ans %= mod
        ans += 2 ** (cnt_zero_now - 1)
        print(ans % mod)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
from operator import xor


N = int(input())
A = list(map(int, input().split()))

MOD = 10**9 + 7

acc = list(accumulate(A, xor))
M = max(acc)
dp = [[0, 0, 0] for _ in range(M + 1)]
z = 0
for x in acc:
    if x == 0:
        z += 1
    else:
        dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        dp[x][2] = z
for x in range(1, M + 1):
    dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
ans = (
    dp[acc[-1]][1] + 1 if acc[-1] != 0 else
    sum(dp[x][0] for x in range(1, M + 1)) + pow(2, acc.count(0) - 1, MOD)
) % MOD


print(ans)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=[0]*N
mod=10**9+7
B[0]=A[0]
for i in range(1,N):
    B[i]=A[i]^B[i-1]
F=[0]*(1<<20)
dp=[1]*(1<<20)
dp1=[0]*(1<<20)
x=1

for i in range(N):
    if B[i]==0:
        x+=1
    dp[B[i]]+=dp1[B[i]]*(x-F[B[i]])
    dp[B[i]]%=mod
    dp1[B[i]]+=dp[B[i]]
    dp1[B[i]]%=mod
    F[B[i]]=x
    

if B[-1]!=0:
    print(dp[B[-1]])
else:
    ans=pow(2,x-2,mod)
    for i in range(1,1<<20):
        ans+=dp1[i]
        ans%=mod
    print(ans)

Solution (Python):
from collections import defaultdict
mod=10**9+7
n=int(input())
A=tuple(map(int,input().split()))
Acc=[0]*n
for i,a in enumerate(A):
    if i==0:
        Acc[0]=a
    else:
        Acc[i]=Acc[i-1]^a

def solve(Acc):
    total_0=0
    dp_0=defaultdict(lambda: 1)
    dp_x=defaultdict(int)
    cnt_0=defaultdict(int)
    for a in Acc:
        if a:
            if a not in dp_x:
                dp_x[a]=1
                cnt_0[a]=total_0
            else:
                dp_0[a]=(dp_0[a]+dp_x[a]*(total_0-cnt_0[a]))%mod
                cnt_0[a]=total_0
                dp_x[a]=(dp_x[a]+dp_0[a])%mod
        else:
            total_0+=1
    if Acc[-1]:
        return dp_0[Acc[-1]]
    return (sum(dp_x.values())+pow(2,total_0-1,mod))%mod

print(solve(Acc))

Solution (Python):
def mod_pow(a: int, n: int, mod: int)->int:
    '''a の n 乗を計算します。
    '''
    res = 1
    while n > 0:
        if n & 1:
            res = (res * a) % mod
        a = (a * a) % mod
        n >>= 1
    return res


def xor_partitioning(N: int, A: list)->int:
    MOD = 10**9 + 7

    
    
    dp = [[0, 1] for _ in range(1 << 20)]
    memo = [0] * (1 << 20)

    b = 0
    num_zero = 0

    for a in A:
        b ^= a

        if b == 0:
            num_zero += 1
        else:
            dp[b][1] += dp[b][0] * (num_zero-memo[b])
            dp[b][1] %= MOD

            dp[b][0] += dp[b][1]
            dp[b][0] %= MOD

            memo[b] = num_zero

    if b > 0:
        return dp[b][1]

    return (sum(_dp[0] for _dp in dp) + mod_pow(2, num_zero-1, MOD)) % MOD


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]

    ans = xor_partitioning(N, A)
    print(ans)

Solution (Python):
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b

mod = 7 + 10 ** 9

def solve():
    N = int(single_input())
    A = [int(a) for a in line_input()]

    DP = [[0, 1] for i in range(2 ** 20)]
    memo = [0] * (2 ** 20)
    cumulative_xor = 0
    zeros = 0
    for i in range(N):
        cumulative_xor ^= A[i]
        if cumulative_xor == 0: zeros += 1  
        else:
            DP[cumulative_xor][1] += DP[cumulative_xor][0] * (zeros - memo[cumulative_xor])
            DP[cumulative_xor][1] %= mod
            DP[cumulative_xor][0] += DP[cumulative_xor][1]
            DP[cumulative_xor][0] %= mod
            memo[cumulative_xor] = zeros

    if cumulative_xor > 0: print(DP[cumulative_xor][1])
    else:
        ans = pow(2, zeros - 1, mod)
        for i in range(2**20): 
            ans += DP[i][0]
            ans %= mod
        print(ans)
        
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N 
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [1]*(m+1)
cnt = [0]*(m+1)
z = 0 

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z
    


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod) 
    for i in range(1,m+1):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N 
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [1]*(m+1)
cnt = [0]*(m+1)
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1,m+1):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N 
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [1]*(m+1)
cnt = [0]*(m+1)
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1,m+1):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N 
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [True]*(m+1)
dp[1] = [False]*(m+1)
cnt = [0]*(m+1)
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1,m+1):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

dp = [[not j for i in range(1<<20)] for j in range(2)]
cnt = [0 for i in range(1<<20)]
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z

if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1, 1<<20):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

XOR=[0]
for a in A:
    XOR.append(XOR[-1]^a)

ZEROS=[0]
for xor in XOR:
    if xor==0:
        ZEROS.append(ZEROS[-1]+1)
    else:
        ZEROS.append(ZEROS[-1])

if XOR[-1]!=0:
    SUBJ=XOR[-1]
    SUBJ_LIST=[]

    for j in range(N+1):
        if XOR[j]==SUBJ:
            SUBJ_LIST.append(j)

    

    ZERO=1
    NOW=0

    for i in range(len(SUBJ_LIST)):
        ZERO+=NOW*(ZEROS[SUBJ_LIST[i]]-ZEROS[SUBJ_LIST[i-1]])
        NOW+=ZERO

        

    print(ZERO%mod)

else:
    SET=set(XOR)
    
    from collections import defaultdict
    SUBJ=defaultdict(list)
    for j in range(1,N+1):
        SUBJ[XOR[j]].append(j)

    ANS=1<<(ZEROS[-1]-2)

    for subj in SUBJ:
        if subj==0:
            continue
        ZERO=1
        NOW=0

        for i in range(len(SUBJ[subj])):
            
            ZERO=(ZERO+NOW*(ZEROS[SUBJ[subj][i]]-ZEROS[SUBJ[subj][i-1]]))%mod
            NOW=(NOW+ZERO)%mod

        
        ANS=(ANS+NOW)%mod

    print(ANS%mod)

Solution (Python):
from itertools import accumulate
from operator import xor


def solve(acc):
    MOD = 10 ** 9 + 7
    cnt0 = 0
    dp0 = {}
    dp1 = {}
    last_0 = {}
    for a in acc:
        if a == 0:
            cnt0 += 1
        else:
            if a not in dp1:
                dp0[a] = 1
                dp1[a] = 1
                last_0[a] = cnt0
            else:
                bw0 = cnt0 - last_0[a]
                if bw0 > 0:
                    dp0[a] = (dp0[a] + dp1[a] * bw0) % MOD
                    last_0[a] = cnt0
                dp1[a] = (dp1[a] + dp0[a]) % MOD

    if acc[-1] == 0:
        return (pow(2, cnt0 - 1, MOD) + sum(dp1.values())) % MOD
    else:
        return dp0[acc[-1]]


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
print(solve(acc))

Solution (Python):
from collections import defaultdict
from itertools import accumulate
from operator import xor


def solve(acc):
    MOD = 10 ** 9 + 7
    cnt0 = 0
    dp0 = defaultdict(lambda: 1)
    dp1 = defaultdict(lambda: 0)
    last_0 = defaultdict(lambda: 0)
    for a in acc:
        if a == 0:
            cnt0 += 1
        else:
            if a not in dp1:
                dp1[a] = 1
                last_0[a] = cnt0
            else:
                bw0 = cnt0 - last_0[a]
                if bw0 > 0:
                    dp0[a] = (dp0[a] + dp1[a] * bw0) % MOD
                    last_0[a] = cnt0
                dp1[a] = (dp1[a] + dp0[a]) % MOD

    if acc[-1] == 0:
        return (pow(2, cnt0 - 1, MOD) + sum(dp1.values())) % MOD
    else:
        return dp0[acc[-1]]


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
print(solve(acc))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(n)]
s[0] = a[0]
for i in range(1, n):
  s[i] = s[i-1]^a[i]

MOD = 10**9+7
dp = [[not j for i in range(1<<20)] for j in range(2)]
cnt = [0 for i in range(1<<20)]
z = 0
for i in range(n):
  if s[i]==0:
    z += 1
  dp[0][s[i]] = (dp[0][s[i]]+dp[1][s[i]]*(z-cnt[s[i]])%MOD)%MOD
  dp[1][s[i]] = (dp[1][s[i]]+dp[0][s[i]])%MOD
  cnt[s[i]] = z

if s[n-1]:
  print(dp[0][s[n-1]])
else:
  ans = pow(2, z-1, MOD)
  for i in range(1, 1<<20):
    ans = (ans+dp[1][i])%MOD
  print(ans)

Solution (Python):
import sys
from collections import defaultdict
from itertools import accumulate
from operator import xor


def solve_0(acc):
    MOD = 10 ** 9 + 7
    cnt_0 = 0
    counts = defaultdict(list)
    last_0 = {}
    for a in acc:
        if a == 0:
            cnt_0 += 1
        else:
            cnt = counts[a]
            if len(cnt) == 0:
                cnt.append(1)
                last_0[a] = cnt_0
            else:
                btw_0 = cnt_0 - last_0[a]
                if btw_0 > 0:
                    cnt.append(btw_0)
                    cnt.append(1)
                    last_0[a] = cnt_0
                else:
                    cnt[-1] += 1

    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        dp0 = 1
        dp1 = cnt[0]
        for c0, c1 in zip(cnt[1::2], cnt[2::2]):
            dp0 = (dp0 + dp1 * c0) % MOD
            dp1 = (dp1 + dp0 * c1) % MOD
        ans = (ans + dp1) % MOD

    return ans


def solve_1(acc):
    MOD = 10 ** 9 + 7
    common = acc[-1]
    dp0 = 1
    dp1 = 0
    for a in acc:
        if a == 0:
            dp0 = (dp0 + dp1) % MOD
        elif a == common:
            dp1 = (dp1 + dp0) % MOD
    return dp0


n = int(input())
aaa = list(map(int, input().split()))
if 'PyPy' in sys.version:
    acc = [0] * n
    t = 0
    for i in range(n):
        t = acc[i] = t ^ aaa[i]
else:
    acc = list(accumulate(aaa, func=xor))

if acc[-1] == 0:
    print(solve_0(acc))
else:
    print(solve_1(acc))

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





mod = 10**9 + 7


class Counter:
    def __init__(self, zerocount):
        self.incr = 1
        self.prev_zerocount = zerocount
        self.count = 1


def main():
    n = intin()
    alist = intina()

    xorlist = []
    xor = 0
    for a in alist:
        xor = a ^ xor
        xorlist.append(xor)

    zerocount = 0
    counters = {}

    for xor in xorlist:
        if xor == 0:
            zerocount += 1
            continue
        if xor not in counters:
            counters[xor] = Counter(zerocount)
            continue

        prev_incr = counters[xor].incr
        prev_zerocount = counters[xor].prev_zerocount
        prev_count = counters[xor].count

        incr = modmlt(zerocount - prev_zerocount, prev_count)
        incr = modadd(incr, prev_incr)

        counters[xor].incr = incr
        counters[xor].prev_zerocount = zerocount
        counters[xor].count = modadd(prev_count, incr)

    if xorlist[-1]:
        print(counters[xorlist[-1]].incr)
    else:
        zerosum = pow(2, zerocount - 1, mod)
        xorsum = sum([counter.count for counter in counters.values()]) % mod
        print(modadd(zerosum, xorsum))


if __name__ == '__main__':
    main()