You are given _n_ integers _a_1, _a_2, ..., _a__n_. 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:
* First, all integers in _L_ are padded with leading zeros so they are all the same length as the maximum length number in _L_.
* We will construct a string where the _i_\-th character is the minimum of the _i_\-th character in padded input numbers.
* The output is the number representing the string interpreted in base 10.
For example _f_(10, 9) = 0, _f_(123, 321) = 121, _f_(530, 932, 81) = 30.
Define the function
Here, denotes a subsequence.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.
## Input
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, _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 999 999) — the elements of the list.
## Output
Output a single integer, the answer to the problem.
[samples]
## Note
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.
你被给定 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]。记这个整数列表为 #cf_span[T]。
定义函数 #cf_span[f(L)]，它接受一个非空整数列表 #cf_span[L]。
该函数将输出另一个整数，如下所示：
例如，#cf_span[f(10, 9) = 0]，#cf_span[f(123, 321) = 121]，#cf_span[f(530, 932, 81) = 30]。
定义函数
换句话说，#cf_span[G(x)] 是对所有非空子序列 #cf_span[S] ⊆ #cf_span[T]，若 #cf_span[f(S) = x]，则将这些子序列的元素和的平方求和，再对 #cf_span[1 000 000 007] 取模，最后乘以 #cf_span[x]（最后一项乘法不取模）。
你希望计算 #cf_span[G(0), G(1), ..., G(999 999)]。为减少输出大小，请输出这些值的异或和，其中 表示按位异或运算符。
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。
第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。
输出一个整数，即问题的答案。
对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或结果为 #cf_span[292 711 924]。
例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时均得到 #cf_span[123]。
对于第二个样例，我们有
对于最后一个样例，我们有 ，其中 是二项式系数。
## Input
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。
## Output
输出一个整数，即问题的答案。
[samples]
## Note
对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或结果为 #cf_span[292 711 924]。例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时均得到 #cf_span[123]。对于第二个样例，我们有 对于最后一个样例，我们有 ，其中 是二项式系数。