Sakuyalove has an array $$$a$$$ with $$$n+1$$$ integers $$$a_0,a_1,...,a_n$$$. She wants to build two arrays $$$b, c$$$ such that: $$$$$$ b_k=\sum\limits_{i=0}^{k}C_k^i(-1)^ia_i\mod 1000000007 $$$$$$
$$$$$$ c_k=\sum\limits_{i=0}^{k}C_k^i(-1)^ib_i\mod 1000000007 $$$$$$ for $$$k=0,1,...,n$$$, where $$$C_k^i=\frac{k!}{i!(k-i)!}$$$ for integer $$$i, k(0\le i\le k)$$$.
Now Sakuyalove wants to know the answer of $$$c_0\oplus c_1\oplus ...\oplus c_n$$$(the operator "$$$\oplus$$$" means XOR operation). Please help her.
The input contains two lines.
The first line contains one integer $$$n(1\le n\le 10^6)$$$, which describes the size of array $$$a$$$ is $$$n+1$$$.
The second line contains $$$n+1$$$ integers $$$a_0,a_1,...,a_n(0\le a_i \lt 10^9+7)$$$ separated by space, which describes the element of array $$$a$$$.
The output contains one line with one integer, which is the answer of $$$c_0\oplus c_1\oplus ...\oplus c_n$$$.
1 0 1
1
7 25 34 18 26 0 55 37 11
42
1 1000000006 73741826
1073740804
For the first sample input, we have: $$$n = 1, a_0=0,a_1=1$$$. Then we can calculate:
$$$b_0=a_0\mod 1000000007=0$$$,
$$$b_1=(a_0-a_1)\mod 1000000007 = 1000000006$$$,
$$$c_0=b_0\mod 1000000007=0$$$,
$$$c_1=(b_0-b_1)\mod 1000000007=1$$$.
So the answer is $$$c_0\oplus c_1=0\oplus 1=1$$$.
