Problem:
 Score : 700 points    Problem Statement Given is a sequence of N digits a_1a_2\ldots a_N , where each element is 1 , 2 , or 3 .
Let x_{i,j} defined as follows:   x_{1,j} := a_j  \quad ( 1 \leq j \leq N )  x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} |  \quad ( 2 \leq i \leq N and 1 \leq j \leq N+1-i )   Find x_{N,1} .      Constraints  2 \leq N \leq 10^6  a_i = 1,2,3  (1 \leq i \leq N)         Input Input is given from Standard Input in the following format:  N  a_1 a_2 \ldots a_N       Output Print x_{N,1} .        Sample Input 1 4
1231      Sample Output 1 1  x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1 .  x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2 .  x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1 .  Finally, x_{4,1} = |0-1| = 1 , so the answer is 1 .       Sample Input 2 10
2311312312      Sample Output 2 0

Solution (Python):

"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
import sys

N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))
   
all_odd = 0
kai = [0] * N

if (0 not in a) and (1 not in a):
    print(0)
    sys.exit()
if (1 not in a) and (2 not in a):
    print(0)
    sys.exit()
if (0 not in a) and (2 not in a):
    print(0)
    sys.exit()
    
for k in range(1,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] == kai[k] + kai[N-1-k] and a[k] == 1:
        all_num += 1

if all_num % 2 == 1:
    print(1)
elif 1 in a:
    print(0)
else:
    for i in range(N):
        a[i] = a[i]/2
    for k in range(N):
        if kai[-1] <= kai[k] + kai[N-1-k] and a[k] == 1:
            all_num += 1
    if all_num % 2 == 1:
        print(2)
    else:
        print(0)

Solution (Python):

"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
import sys

N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))
   
all_odd = 0
kai = [0] * N

if (0 not in a) and (1 not in a):
    print(0)
    sys.exit()
if (1 not in a) and (2 not in a):
    print(0)
    sys.exit()
if (0 not in a) and (2 not in a):
    print(0)
    sys.exit()
    
for k in range(1,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] <= kai[k] + kai[N-1-k] and a[k] == 1:
        all_num += 1

if all_num % 2 == 1:
    print(1)
elif 1 in a:
    print(0)
else:
    for i in range(N):
        a[i] = a[i]/2
    for k in range(N):
        if kai[-1] <= kai[k] + kai[N-1-k] and a[k] == 1:
            all_num += 1
    if all_num % 2 == 1:
        print(2)
    else:
        print(0)

Solution (Python):
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)


def nxor(x,n,k):
    if (n&k) == k:
        return x
    else:
        return 0


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],n - 1,i)
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],n - 1,i)
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
n=int(input())
a=[int(t)-1 for t in input()]
f=1
if 1 not in a:
	a=[x//2 for x in a]
	f=2
s=sum([x for i,x in enumerate(a) if (n-1)&i==i])
print(s%2*f)


"""
メモ
初めに各要素から1を差し引いても同じ
数列に1が存在する⇒答えは2になり得ない
⇒答えの偶奇を判定できればいい⇒各要素の寄与分を考える
「nCrの偶奇 == (n&r==r)」 の関係（Lucasの定理から導かれる）が利用できる！
数列が0,2のみの場合は2を1に読み替えて同様
参考： https://mathtrain.jp/lucastheorem
"""

Solution (Python):
n = int(input())
string = input()
a = []
a_01 = []
a_02 = []
bit_1 = 0
for i in range(n):
    a.append(int(string[i])-1)
    a_01.append((int(string[i])-1)%2)
    a_02.append((int(string[i])-1)//2)
    if int(string[i])-1 == 1: bit_1 = 1


num_lst = [0 for i in range(n)]
for i in range(1, n):
    p = i
    cnt = 0
    while p % 2 == 0:
        p = p / 2
        cnt += 1
    num_lst[i] = cnt
n_1Ci = [0 for i in range(n)]
for i in range(1, n):
    n_1Ci[i] = n_1Ci[i-1] + num_lst[n-i] - num_lst[i]



cnt_01 = [0, 0]
for i in range(n):
    cnt_01[a_01[i]] += 1 if n_1Ci[i] == 0 else 0
if cnt_01[1] % 2 == 1:
    print(1)
    exit()


if bit_1 == 1:
    print(0)
    exit()


cnt_02 = [0, 0]
for i in range(n):
    cnt_02[a_02[i]] += 1 if n_1Ci[i] == 0 else 0
if cnt_02[1] % 2 == 1:
    print(2)
else:
    print(0)

Solution (Python):
def is_odd_binomial(n, m):
    return ((~n) & m) == 0


N = int(input())
a = list(map(lambda x: int(x) - 1, input()))

parity = sum(a[i] for i in range(N) if is_odd_binomial(N - 1, i))
if parity % 2 == 1:
    ans = 1
elif 1 in a:
    ans = 0
elif parity % 4 == 2:
    ans = 2
else:
    ans = 0

print(ans)

Solution (Python):
N = int(input())
A = input()

S = [int(A[i])-1 for i in range(N)]
Lucas = [0 for i in range(N)]
D = {0: 1}
base, m = 1, N - 1
while m != 0:
  if m % 2 == 1:
    L = [i for i in D]
    for i in L:
      D[i+base] = 1
  m //= 2
  base *= 2
for i in D:
  Lucas[i] = 1
oddness = 0
for i in range(N):
  if S[i] % 2 != 0:
    oddness += Lucas[i]
    oddness %= 2

if oddness == 1:
  print(1)
else:
  if 1 in S:
    print(0)
  else:
    S = [S[i]//2 for i in range(N)]
    oddness = 0
    for i in range(N):
      if S[i] % 2 != 0:
        oddness += Lucas[i]
        oddness %= 2
    if oddness == 1:
      print(2)
    else:
      print(0)

Solution (Python):
N = int(input())
A = list(map(lambda a: int(a) - 1, input()))

prd = 1
if all(a % 2 == 0 for a in A):
    prd = 2
    A = [a // 2 for a in A]

ans = 0
for i in range(N):
    if (N - 1) & i == i:
        ans ^= A[i] % 2

print(prd * ans)

Solution (Python):
N = int(input())
S = input()
a = [int(s)-1 for s in S]


from collections import defaultdict

r = 1
d = defaultdict(int)
while 2**r  <= N:
  for i in range(1,N):
    if i*(2**r) <= N:
      d[i*(2**r)] += 1
    else:
      break
  r+=1

def calc(list_of_int):
  
  length = len(list_of_int)
  res = list_of_int[0]
  
  keisu = 0
  for i,r in zip(list_of_int[1:], range(N-1)):
    keisu += d[N-r-1]-d[r+1]
    res = (res + ((2 if keisu>0 else 1)*i) )% 2
  return res

if 1 in a:
  print(calc(a))
else:
  print(calc(list(map(lambda x:x//2,a)))*2)

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

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


def contains(n):
    t = n&-n
    return t.bit_length()


def solve1(A, D):
    is1 = False
    cmb_e = 0
    for i, a in enumerate(A):
        if a and cmb_e == 0:
            is1 = not is1
        cmb_e += contains(D-1-i) - contains(i+1)
    return is1

B = [abs(A[i]-A[i+1]) for i in range(N-1)]
if 1 in set(B):
    C = [b%2 for b in B]
    is1 = solve1(C, N-1)
    print(1 if is1 else 0)
else:
    C = [b//2 for b in B]
    is2 = solve1(C, N-1)
    print(2 if is2 else 0)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))




def lucas(B, r):
    
    R = bin(r)[2:]
    for x, y in zip(B[::-1], R[::-1]):
        if x == '0' and y == '1':
            return 0
    return 1

N = ir()
A = np.array(list(map(int, sr())))
A = np.abs(np.diff(A))
N -= 1
bl = False
if 1 not in set(A):
    bl = True
    A //= 2


result = 0
A = A.tolist()
B = bin(N-1)[2:]
for i, a in enumerate(A):
    result += a * lucas(B, i)
result %= 2

print(result * 2 if bl else result)

Solution (Python):
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]

if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) ))
print((s%2)*factor)

Solution (Python):
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]

if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
  s = s%2
print((s%2)*factor)

Solution (Python):
N=int(input())
A=[int(a)-1 for a in input()]
r=2-(1 in A)
print(sum([A[i]&r and (N-1&i)==i for i in range(N)])%2*r)

Solution (Python):
N=int(input());A=[int(a)-1 for a in input()];print(sum([A[i] for i in range(N) if N-1&i==i])%(4>>(1 in A)))

Solution (Python):
N=int(input());A=[int(a)-1 for a in input()];print(sum([A[i] for i in range(N) if N-1&i==i])%(4>>int(1 in A)))

Solution (Python):
N=int(input())
A=[int(a)-1 for a in input()]
r=1 if 1 in A else 2
print(sum([1 if A[i]&r and (N-1&i)==i else 0 for i in range(N)])%2*r)

Solution (Python):


import numpy as np



N = int(input())
a = input()


def main():
    num, fac = [0] * (N + 1), [0] * (N + 1)
    num[0] = num[1] = 0
    fac[0] = fac[1] = 0
    for i in range(2, N, 2):
        num[i] = 1 + num[i // 2]
        fac[i] = fac[i+1] = fac[i-1] + num[i]
    
    m = np.zeros(N, dtype=int)
    for i in range(N):
        if fac[N-1] == fac[i] + fac[N-1-i]:
            m[i] = 1
    
    x = np.array([int(e) for e in a])
    x -= 1

    if (x * m).sum() % 2 == 1:
        print(1)
        return
    if 1 in x:
        print(0)
        return

    x //= 2
    if (x * m).sum() % 2 == 1:
        print(2)
    else:
        print(0)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(a)-1 for a in input()]

r = 1 if 1 in A else 2

def parity_of_nCk(n, k):
    return (n&k)==k

ans = 0
for i, a in enumerate(A):
    if a & r:
        if parity_of_nCk(N-1,i):
            ans ^= 1

print(ans*r)

Solution (Python):
def Lucas(n, k):
    if n&k == k:
        return 1
    else:
        return 0

n = int(input())
a = list(map(int, list(input())))
odd = 0
cnt = 0
for i in range(n):
    a[i] -= 1
    if a[i] == 1:
        odd += Lucas(n-1, i)
        cnt = 1
if odd % 2 == 1:
    print(1)
else:
    if cnt == 1:
        print(0)
    else:
        for i in range(n):
            a[i] //= 2
            if a[i] == 1:
                odd += Lucas(n-1, i)
        print(odd%2 * 2)

Solution (Python):
from collections import Counter, defaultdict


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



A = [abs(x - y) for x, y in zip(A, A[1:])]
N -= 1


def solve(A):
    N = len(A)

    def fact(n):
        if n == 0:
            return 1
        return n * fact(n - 1)

    def nCr(n, r):
        return fact(n) // (fact(n - r) * fact(r))

    def nCrMod2(n, r):
        return 0 if (n ^ r) & r else 1
        
        while r:
            if r % 2 and not n % 2:
                return 0
            n //= 2
            r //= 2
        return 1

    onlyZeroesAndTwos = Counter(A)[1] == 0

    ans = None
    if onlyZeroesAndTwos:
        ans = 2 * (sum(nCrMod2(N - 1, i) * (A[i] // 2) for i in range(N)) % 2)
    else:
        ans = sum(nCrMod2(N - 1, i) * A[i] for i in range(N)) % 2

    if False:
        import numpy as np

        
        
        
        
        
        
        
        
        
        
        
        
        

        
        mat = np.zeros((N, N), dtype=np.int64)
        for i in range(N - 1):
            mat[i][i] = 1
            mat[i][i + 1] = 1

        vec = np.array(A, dtype=np.int64)

        for t in range(N):
            M = np.linalg.matrix_power(mat, t)
            print("t", t)
            print("M^t", M)
            print("v_t", np.matmul(M, vec)[: N - t] % 4)
            print()
        
        for i in range(N):
            assert np.linalg.matrix_power(mat, N - 1)[0][i] == nCr(N - 1, i)

        mod4 = sum(nCr(N - 1, i) * A[i] for i in range(N)) % 4

        
        ans2 = mod4
        if not onlyZeroesAndTwos:
            
            
            ans2 = mod4 % 2
        
        assert ans == ans2
    return ans


print(solve(A))

if False:
    
    from itertools import product

    for N in range(2, 7):
        print("N", N)

        groups = defaultdict(list)
        for A in product([0, 1, 2], repeat=N):
            temp = list(A)
            for i in range(N - 1):
                temp = [abs(x - y) for x, y in zip(temp, temp[1:])]
            assert len(temp) == 1
            groups[temp[0]].append(A)

        for k, v in groups.items():
            print("ans", k)
            for A in v:
                assert k == solve(A)
                print("\t", A)
        print()

Solution (Python):

import sys

def solve(N: int, a: str):
    a = [int(a[i])-1 for i in range(N)]
    zeroone = [a[i]%2 for i in range(N)]

    SUM = 0
    comb = [0]*N
    comb[0] = 1

    for i in range(1, N):
        comb[i] = 1 if (N-1)&i == i else 0

    for i in range(N):
        SUM += zeroone[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(1)
        return
    
    if 1 in a:
        print(0)
        return
    
    
    zerotwo = [a[i]//2 for i in range(N)]

    SUM = 0
    for i in range(N):
        SUM += zerotwo[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(2)
        return
    
    print(0)
    return


def main():
    N = int(input())  
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
num_mod = [0]*N
for i in range(1,N):
  tmp = 0
  t = i
  while t%2==0:
    t//=2
    tmp+=1
  num_mod[i] = num_mod[i-1]+tmp
  
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Solution (Python):
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if((N-1)&i)==i:
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Solution (Python):
import math

N = int(input())
a = list(map(int, list(input())))

x = []
while len(x) != 1:
	inx = 1 << (math.floor(math.log2(N)) - 1)

	N -= inx
	x = [0] * N
	for i in range(N):
		x[i] = abs(a[i] - a[i + inx])

	a = x

print(x[0])

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    A = [ord(a)-48 for a in args[1]]

    A = [abs(A[i]-A[i+1]) for i in range(n-1)]
    r = 2 if A.count(1) == 0 else 1

    ret = 0
    for i in range(n-1):
        ret += (A[i]//r)*(n-2 == (i | (n-2-i)))

    return str((ret % 2)*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc043/tasks/agc043_b

まず、1度計算して 0,1,2の問題にしてよい

1が含まれているとき、答えが2にならない証明
途中経過に2が含まれていないと、2にはならない
→1が含まれているかつ、偶数がある場合、次は必ず1が含まれる
→偶数が消えない場合、最後まで1が残る
→最後まで2が消えない場合、最後は1になってしまうので×
よって、答えが2になるのは0,2のみのとき
→この時は2で割っておいて、最後に2を掛ければよい
"""
N = int(input())

div2_num = [0]
for i in range(1,N+1):

    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i //= 2
    div2_num.append(div2_num[-1] + cnt)



def EO_nCr(n,r): 

    if div2_num[n] - (div2_num[n-r] + div2_num[r]) > 0:
        return 0
    else:
        return 1



A = list(map(int,list(input())))


a = []

for i in range(N-1):
    a.append(abs(A[i]-A[i+1]))



if 1 not in a:
    for i in range(N-1):
        a[i] = a[i] // 2
    lastk = 2
else:
    lastk = 1


ans = 0

for i in range(N-1):

    ans ^= (a[i]%2) * EO_nCr(N-2,i)

    

print (ans * lastk)

Solution (Python):
import sys
n=int(input())
a=list(input())
A=[]
for i in range(n):
  a[i]=int(a[i])-1
  A.append(a[i]%2)

xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=A[i]
if xorct==1:
  print(1)
  sys.exit()

if 1 in a:
  print(0)
  sys.exit()

for i in range(n):
  a[i]=a[i]//2
xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=a[i]
if xorct==1:
  print(2)
  sys.exit()

print(0)

Solution (Python):
def main():
    n=int(input())
    A=list(map(lambda x: int(x)-1,list(input().strip())))
    ans=1
    if not 1 in A:
        ans*=2
        for i in range(n):
            A[i]>>=1
    parity=0
    for i in range(n):
        if (n-1)&i==i:
            parity^=A[i]&1
    ans*=parity
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])





if 2 in x:
    flag = True
    x = [1 if i == 2 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 3 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n-1)
if x[0]==1:
    c+=1
for i in range(1,n-1):
    tmp_nck = int((n-1) == (i | (n-1-i)))
    if x[i] == 1:
        c+=tmp_nck
if x[n-1]==1:
    c+=1
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Solution (Python):
def even_or_odd(a):
    ans = a[0] % 2
    for i in range(1, N):
        ans ^= int((N-1) & i == i) & a[i]
    return ans

N = int(input())
a = [x-1 for x in list(map(int, list(input())))]

if even_or_odd([x % 2 for x in a]) == 1:
    print(1)
elif 1 in a:
    print(0)
elif even_or_odd([x//2 for x in a]) == 1:
    print(2)
else:
    print(0)

Solution (Python):
N = int(input())
A = [int(a) - 1 for a in input()]
s = sum([a for i, a in enumerate(A) if (N - 1) & i == i])
print(s % (2 if 1 in A else 4))

Solution (Python):
def comb(n, r):
  return n == ( r | (n - r) ) 
  
N=int(input())
S=input()
x=0;
b=1;
for i in range(N):
  s=int(S[i])%2;
  x=(x+s*(comb(N-1,i)))%2;
  b*=s%2;
if(x%2 or b==0):
  print(x%2);exit();
x=0;
for i in range(N):
  s=(int(S[i])//2)%2;
  x=(x+s*(comb(N-1,i)))%2;

print((x%2)*2);

Solution (Python):
n = int(input())

s = input()
a = []
for i in range(n - 1):
    a.append(abs(int(s[i]) - int(s[i + 1])))

ans = []
for r in range(n - 1):
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)

Solution (Python):
n = int(input())
a = list(map(int, input()))
if n <= 1:
    print(a[0])
    exit()
for i in range(n - 1):
    a[i] = abs(a[i + 1] - a[i])
a.pop()
n -= 1
def bc(u, v):
    return (u & v) == v
def solve(t):
    ans = 0
    for i in range(n):
        if a[i] == 1:
            ans ^= bc(n - 1, i)
    print(ans * t)
if 1 in a:
    solve(1)
else:
    for i in range(n):
        a[i] >>= 1
    solve(2)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    a = list(map(lambda x: int(x) - 1, S()))
    ans = 1
    if not 1 in a:
        ans *= 2
        for i in range(n):
            a[i] >>= 1
    res = 0
    for i in range(n):
        
        
        
        
        
        if ((n - 1) & i == i):
            res ^= a[i] & 1
    print(res * ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

if "2" in s: p=2
else: p=3

ans=0
for i in range(n):
    if int(s[i])==p and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1
print(ans if p==2 else ans*2)

Solution (Python):
def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        
        print(*a)











def solve(n, aaa):
    
    if '2' not in aaa:
        factor = '3'
        effect = 2
    else:
        factor = '2'
        effect = 1
    

    try_list = []
    m = n - 1
    while m:
        l = 1 << (m.bit_length() - 1)
        m ^= l
        try_list.append((l, m))
    

    ans = 0
    for i, a in enumerate(aaa):
        if a == factor:
            for l, m in try_list:
                if i >= l:
                    i -= l
                if i == 0:
                    ans ^= effect
                    break
                elif i > m:
                    break
    return ans


n = int(input())
aaa = input()
print(solve(n, aaa))

Solution (Python):
def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        
        print(*a)











def solve(n, aaa):
    
    if '2' not in aaa:
        factor = '3'
        effect = 2
    else:
        factor = '2'
        effect = 1
    

    try_list = []
    m = n - 1
    while m:
        l = 1 << (m.bit_length() - 1)
        m ^= l
        try_list.append((l, m))
    

    ans = 0
    for i, a in enumerate(aaa):
        if a == factor:
            for l, m in try_list:
                if i >= l:
                    i -= l
                if i == 0:
                    ans ^= effect
                    break
                elif i > m:
                    break
    return ans


n = int(input())
aaa = input()
print(solve(n, aaa))

Solution (Python):
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

ans=0
for i in range(n):
    if int(s[i])==2 and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1

if ans==1: print(1)
elif "2" in s: print(0)
else:
    ans=0
    for i in range(n):
        if int(s[i])==3 and frac[n-1]-frac[i]-frac[n-1-i]==0:
            ans^=1
    print(ans*2)

Solution (Python):
N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N+1)]
i = 2
while i < N:
	for j in range(i, N+1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N+1):
	sum_t.append(sum_t[-1] + t[i])

x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]


def isCombOdd(n,k):
	bunshi = sum_t[n] - sum_t[n-k]
	bunbo = sum_t[k]
	return bunshi == bunbo

f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]

candidate = 1 if f1 else 2
ans = 0
for i in range(N-1):
	if x[i] > 0 and isCombOdd(N-2, i):
		ans = 1 - ans

print(0 if ans == 0 else candidate)

Solution (Python):
n = int(input())
aa = list(map(lambda x: int(x)-1, list(input())))

def parity(n, r):
    
    
    if n <= 1:
        return 1
    if r == 1:
        return n % 2
    if r == 0:
        return 1
    if n % 2 == 0 and r % 2 != 0:
        return 0
    return parity(n//2, r//2)

def ab(x):
    if x < 0:
        return -x
    return x

ans = 0
for i, a in enumerate([a % 2 for a in aa]):
    p = parity(n-1, i)
    if p == 1:
        ans = ab(ans - a)

if ans == 1:
    print(1)
    exit(0)

if 1 in aa:
    print(0)
    exit(0)

ans = 0
for i, a in enumerate([a // 2 for a in aa]):
    p = parity(n-1, i)
    if p == 1:
        ans = ab(ans - a)
print(ans * 2)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())
a = input()


def bit_count(i):
    res = 0
    while ((i>0) and (i&1 == False)):
        i  >>=1
        res += 1
        
    return res

f = [0]
for i in range(N//2):
    f.append(f[-1] + bit_count(N-1-i) - bit_count(i+1))

def nCr(n, r):
    if r > n-r: r = n-r
    if f[r] == 0:   
        return 1
    else:
        return 0

def main():
    ans = 0
    for i in range(N):
        now = int(a[i]) - 1     
        if now%2:
            
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2
    if ans:
        return ans

    if '2' in a:    
        return 0

    ans = 0
    for i in range(N):
        now = (int(a[i]) - 1) // 2     
        if now%2:
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2
    return ans*2    

print(main())

Solution (Python):
N = int(input())
a = list(map(int, list(input())))

def mod2_pascal(n):
    res = []
    for r in range(n+1):
        res.append(1 if n == (r | (n-r)) else 0)
    return res

b = []

if N >= 3:
    for i in range(N-1):
        b.append(abs(a[i]-a[i+1]))
    mod2_line = mod2_pascal(N-2)
    ans = 0
    for i in range(N-1):
        if mod2_line[i] == 1:
            ans += b[i]
    if b.count(0) == N-1 - b.count(2):
        b_divided_by_2 = list(map(lambda x:x//2, b))
        for i in range(N - 1):
            if mod2_line[i] == 1:
                ans += b_divided_by_2[i]
        if ans%2 == 1:
            print(2)
        else:
            print(0)
    else:
        print(ans % 2)

else:
    print(abs(a[1]-a[0]))

Solution (Python):
import math
n=int(input())
alist=input()
blist=[]
swit=0
for i in range(n-1):
    now=abs(int(alist[i+1])-int(alist[i]))
    if now==1:
        swit=1
    blist.append(now)
if swit==1:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=0
else:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=1
dekai=100
while len(blist)>1:
    clist=[]
    dekai=math.floor(math.log(len(blist),2))
    katamari=2**dekai
    kosu=len(blist)-katamari+1
    nanko=0
    for i in range(katamari):
        if blist[i]==1:
            nanko+=1
    clist.append(nanko%2)
    for i in range(kosu-1):
        nanko+=blist[katamari+i]-blist[i]
        clist.append(nanko%2)
    blist=clist

if swit==1:
    print(blist[0])
else:
    print(blist[0]*2)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N = int(input())
A = list(map(int,input()))
X = 2 in A

while len(A) > 1:
    if len(A) % 2 == 1:
        for i in range(len(A)-1):
            A[i] = abs(A[i]-A[i+1])
        A.pop()
    B = []
    for i in range(len(A)//2):
        B.append(abs(A[i*2]-A[i*2+1]))
    A = B[:]

if X:
    A[0] %= 2
print(A[0])

Solution (Python):
N = int(input())
a = list(map(int, list(input())))
 
while N != 0:
	digit = 1
	while digit < N // 2:
		digit *= 2
 
	x = []
	for i in range(digit, N):
		x.append(abs(a[i - digit] - a[i]))
 
	a = x
	N -= digit
	if len(x) == 1:
		break
 
print(a[0])

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    iS = input().rstrip()

    S = []
    for i in range(N-1):
        S.append(abs(int(iS[i])-int(iS[i+1])))
    N -= 1

    f = FactorialUtils(N)
    n1 = n2 = 0
    for i in range(N):
        t = f.choose(N-1,i)
        
        if S[i] == 1: n1 += t
        elif S[i] == 2: n2 += t
    if n1&1 and n2&1: print(1)
    elif n1&1: print(1)
    elif n2&1 and n1==0: print(2)
    else: print(0)
    

class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n+1)
        for i in range(2, n+1): self.fac[i] = self.fac[i-1] + (i&(-i)).bit_length()

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return 2 if (self.fac[n] - self.fac[n-r] - self.fac[r]) > 0 else 1

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = list(map(int, input()))
if N == 2:
    print(abs(a[0]-a[1]))
    exit()
a1 = [abs(a[i]-a[i+1]) for i in range(N-1)]
if 1 in a1:
    s = 0
    for i in range(len(a1)):
        if ((len(a1)-1) | i) == (len(a1)-1):
            s += a1[i] % 2
    print(s % 2)
else:
    s = 0
    for i in range(len(a1)):
        if ((len(a1)-1) | i) == (len(a1)-1):
            s += a1[i] // 2
    print((s % 2) * 2)

Solution (Python):
n = int(input())
a = input()
a2 = [int(a[i]) for i in range(n)]
n2 = bin(n)
b = [0] * n
c = [1] * (2 ** (len(n2) - 3))
for i in range(len(c)):
    b[i] += c[i]
temp = len(n2) - 4
count = len(c)
while temp>= 0:
    if n2[-1-temp] == "1":
        c = [b[i] for i in range(count)]
        for i in range(count):
            b[i + 2 ** temp] += c[i]
        count += 2 ** temp
    temp -= 1
e = [b[i] % 2 for i in range(len(b))]
d = 0
for i in range(n):
    if e[i] % 2 == 1:
        d += a2[i]
if d % 2 == 1:
    print(1)
else:
    a3 = [abs(a2[i] - a2[i + 1]) for i in range(n - 1)]
    if 1 in a3:
        print(0)
    else:
        n3 = bin(n - 1)
        b = [0] * (n - 1)
        c = [1] * (2 ** (len(n3) - 3))
        for i in range(len(c)):
            b[i] += c[i]
        temp = len(n3) - 4
        count = len(c)
        while temp>= 0:
            if n3[-1-temp] == "1":
                c = [b[i] for i in range(count)]
                for i in range(count):
                    b[i + 2 ** temp] += c[i]
                count += 2 ** temp
            temp -= 1
        e = [b[i] % 2 for i in range(len(b))]
        d = 0
        for i in range(n - 1):
            if e[i] % 2 == 1:
                d += a3[i]
        if d % 4 == 0:
            print(0)
        else:
            print(2)

Solution (Python):
N = int(input())
A = input()
b = []
for i in range(N-1):
    b.append(abs(int(A[i])-int(A[i+1])))
S = 0
p = 0
for i in range(N-1):
    if p == 0:
        S += b[i]
    n = N - 2 - i
    k = i + 1
    if n == 0:
        break
    else:
        while n % 2 == 0:
            p += 1
            n //= 2
        while k % 2 == 0:
            p -= 1
            k //= 2

if S % 2:
    print(1)
else:
    for i in range(N-1):
        if b[i] == 1:
            print(0)
            exit()
    if (S // 2) % 2:
        print(2)
    else:
        print(0)

Solution (Python):
N = int(input())
a = input()

def myc(n):
    ret = 0
    while n % 2 == 0:
        ret += 1
        n //= 2
    return ret

def func(c):
    odd = 0
    count = 0
    if a[0] == c:
        count += 1
    if a[-1] == c:
        count += 1
    for i in range(1, N // 2):
        odd += myc(N-i) - myc(i)
        if a[i] == c and odd == 0:
            count += 1
        if a[-i-1] == c and odd == 0:
            count += 1
    if N % 2 == 1:
        if a[N // 2] == c and odd + myc(N // 2 + 1) - myc(N // 2) == 0:
            count += 1
    return count % 2 == 0

if '2' in a:
    if func('2'):
        print(0)
    else:
        print(1)
else:
    if func('3'):
        print(0)
    else:
        print(2)