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>

using namespace std;

constexpr int MAXN = 1000000;

char X[MAXN + 2];

int main() {
	int N;
	cin >> N >> X;
	int m = 0;
	for(int i = 0; i < N; i++) {
		X[i] -= '1';
		m |= 1 << X[i];
	}
	m = !(m & 2);
	for(int i = 0; i < N; i++)
		if(X[i] == 2)
			X[i] = m;
	int comb = __builtin_ctz(N - 1);
	bool res = X[0] ^ X[N - 1];
	for(int i = 1; i < N - 1; i++) {
		if(comb == 0) res ^= X[i];
		comb += __builtin_ctz(N - 1 - i);
		comb -= __builtin_ctz(i + 1);
	}
	int ans = res ? (m ? 2 : 1) : 0;
	cout << ans << '\n';
}
