CF424C Magic Formulas

People in the Tomskaya region like magic formulas very much. You can see some of them below. Imagine you are given a sequence of positive integer numbers $ p_{1} $ , $ p_{2} $ , ..., $ p_{n} $ . Lets write down some magic formulas: Here, "mod" means the operation of taking the residue after dividing. The expression  means applying the bitwise $ xor $ (excluding "OR") operation to integers $ x $ and $ y $ . The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor". People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence $ p $ , calculate the value of $ Q $ .

The first line of the input contains the only integer $ n $ ( $ 1

The only line of output should contain a single integer — the value of $ Q $ .