Problem: 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_1a_2\ldotsa_N


Output

Print x_{N,1}.

Examples

Input

4
1231


Output

1


Input

10
2311312312


Output

0

Solution (in PYTHON3):

Solution:

"""
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)

#print (div2_num)

def EO_nCr(n,r): #nCr%2を返す

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



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

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 (N-2,i,EO_nCr(N-2,i))

print (ans * lastk)