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
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))

    n = None
    count = 0
    filtered = []
    for a, cnt in ret:
        if a != n:
            n = a
            count = 0
            filtered.append((n, 0))
        count += cnt
        filtered[-1] = (n, count)
    return filtered

#
# A = []
# for _ in range(N):
#     import random
#
#     A.append(random.randint(0, 2))
# ans = test(A)
# print(ans)

# cnt2[n]: n! が 2 で何回割れるか
cnt2 = []
cnt = 0
for n in range(N + 10):
    while n >= 2 and n % 2 == 0:
        n //= 2
        cnt += 1
    cnt2.append(cnt)

# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 1が入ってるとき、2は0と同一視できる
if 1 in A:
    for i in range(len(A)):
        if A[i] == 2:
            A[i] = 0
mod = 2 if 1 in A else 4

ans = 0
n = len(A) - 1
for r in range(len(A)):
    cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
    # cnt = math.factorial(n) // math.factorial(r) // math.factorial(n - r)
    if cnt == 0:
        ans += A[r]
        ans %= mod
    # print(n, r, cnt)
print(ans)


