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

Solution:

import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final String s = scanner.next();

        final List<Integer> list = IntStream.range(0, n)
                .mapToObj(i -> s.charAt(i) - '1')
                .collect(Collectors.toList());

        final int parity = calcParity(list, n);

        if (parity == 1) {
            System.out.println(1);
            return;
        }

        final boolean isOneIncluded = list.stream()
                .anyMatch(i -> i == 1);

        if (isOneIncluded) {
            System.out.println(0);
            return;
        }

        final List<Integer> divedList = list.stream()
                .map(i -> i / 2)
                .collect(Collectors.toList());

        final int divedParity = calcParity(divedList, n);
        if (divedParity == 0) {
            System.out.println(0);
        } else {
            System.out.println(2);
        }
    }

    private static int calcParity(final List<Integer> list, final int n) {
        int parity = list.get(0) ^ list.get(n - 1) % 2;
        final String binary = new StringBuilder(Integer.toBinaryString(n - 1)).reverse().toString();
        for (int i = 1; i < n - 1; i++) {
            final int a = list.get(i);
            final String iString = new StringBuilder(Integer.toBinaryString(i)).reverse().toString();
            int coefficient = 1;
            for (int j = 0; j < binary.length(); j++) {
                if (coefficient == 0) {
                    break;
                }
                coefficient *= combine(binary.charAt(j) - '0', j < iString.length() ? iString.charAt(j) - '0' : 0);
            }
            parity ^= coefficient * a;
        }

        return parity % 2;
    }

    private static int combine(final int n, final int k) {
        return k > n ? 0 : 1;
    }
}