You are given n integers a1, a2, ..., an. Denote this list of integers as T. Let f(L) be a function that takes in a non-empty list of integers L. The function will output another integer as follows: For example f(10, 9) = 0, f(123, 321) = 121, f(530, 932, 81) = 30. Define the function In other words, G(x) is the sum of squares of sum of elements of nonempty subsequences of T that evaluate to x when plugged into f modulo 1 000 000 007, then multiplied by x. The last multiplication is not modded. You would like to compute G(0), G(1), ..., G(999 999). To reduce the output size, print the value , where denotes the bitwise XOR operator. The first line contains the integer n (1 ≤ n ≤ 1 000 000) -- the size of list T. The next line contains n space-separated integers, a1, a2, ..., an (0 ≤ ai ≤ 999 999) -- the elements of the list. Output a single integer, the answer to the problem. For the first sample, the nonzero values of G are G(121) = 144 611 577, G(123) = 58 401 999, G(321) = 279 403 857, G(555) = 170 953 875. The bitwise XOR of these numbers is equal to 292 711 924. For example, , since the subsequences [123] and [123, 555] evaluate to 123 when plugged into f. For the second sample, we have For the last sample, we have , where is the binomial coefficient.