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 <bits/stdc++.h>
#define ll long long
using namespace std;
 
int solve(vector<int> &vec,int n){
  int x=0;
  int m=n-1;
  for(int i=0;i<n;i++){
    if(vec[i]==1){
      x+=((m&i)==i);
    }
  }
  return x%2;
}

int main(){
  int n;
  cin>>n;
  vector<int> vec(n);
  int count=0;
  int z=1;
  string s;
  cin>>s;
  
  for(int i=0;i<n;i++){
    if(s.at(i)=='1'){
      vec[i]=0;
    }
    if(s.at(i)=='2'){
      vec[i]=1;
      count++;
    }
    if(s.at(i)=='3'){
      vec[i]=2;
    }
  }
  
  if(count==0){
    for(int i=0;i<n;i++){
      vec[i]/=2;
    }
    z++;
  }
  
  cout<<solve(vec,n)*z<<endl;
}