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