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())
aa = list(map(lambda x: int(x)-1, list(input())))

def parity(n, r):
    # parity of n choose r
    # via https://math.stackexchange.com/questions/233269/odd-and-even-numbers-in-pascals-triangle-sierpinskis-triangle
    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)