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
#include <stdio.h>

bool exist = false;
int ans = 0;

int main(void){
    int n = 0;{
        int k;
        while((k = getchar_unlocked() - '0') >= 0) n = 10 * n + k;
    }
    const int m = n - 1;
    for(int i = 0; i < n; ++i){
        switch(getchar_unlocked()){
            case '2':
                exist = true;
                if((m | i) == m) ans ^= 1; 
                break;
            case '3':
                if((m | i) == m) ans ^= 2;
        }
    }
    if(exist) putchar_unlocked((ans & 1) ? '1' : '0');
    else putchar((ans & 2) ? '2' : '0');
    putchar('\n');
    return 0;
}