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())
s = list(input())

# mod = 2
# l = 10**6 + 3

# M = [1]  # i!のmod
# m = 1
# for i in range(1, l):
#     m = (m * i) % mod
#     M.append(m)

# def pow(x, y, mod):  # x**y の mod を返す関数
#     ans = 1
#     while y > 0:
#         if y % 2 == 1:
#             ans = (ans * x) % mod
#         x = (x**2) % mod
#         y //= 2
#     return ans

# def inv(x, mod):  # x の mod での逆元を返す関数
#     return pow(x, mod-2, mod)

# # print(inv(8,13))

# MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
# for i in range(l-2, -1, -1):
#     MI[i] = MI[i+1] * (i+1) % mod

# def C(x, y):  # コンビネーション
#     if y < 0 or y > x:
#         return 0
#     elif x > l:  # O(min(y, x-y))
#         y = min(y, x-y)
#         ans = 1
#         for i in range(x, x-y, -1):
#             ans = (ans * i) % mod
#         return (ans * MI[y]) % mod
#     else:  # O(1)
#         ans = M[x]
#         ans = (ans * MI[y]) % mod
#         return (ans * MI[x-y]) % mod


# print(C(3,2))
ans = 0
# print(s)
if s.count("2") == 0:
    # print(s)
    for i in range(n):
        if s[i] == "3":
            # ans += C(n-1, i)%2
            if (n-1)&i == i:
                ans += 1
    # print(ans)
    print(2 * (ans%2))
else:
    for i in range(n):
        if s[i] == "2":
            # ans += C(n-1, i)%2
            if (n-1)&i == i:
                ans += 1
    print(ans%2)