CF772D.Varying Kibibits

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.

给你 $ n $ 个整数 $ a_1,,a_2,,\dots,,a_n $。将该整数列表记为 $ T $。

定义函数 $ f(L) $，其输入为一个非空整数列表 $ L $。

该函数的输出为另一个整数，具体计算方式如下：

• 首先，将 $ L $ 中所有整数用前导零补位，使其长度均等于 $ L $ 中最长数字的长度；
• 然后，构造一个字符串，其中第 $ i $ 个字符为所有补位后输入数字的第 $ i $ 个字符的最小值；
• 最终输出即为该字符串所表示的十进制数。

例如：$ f(10,,9) = 0 $，$ f(123,,321) = 121 $，$ f(530,,932,,81) = 30 $。

定义函数

其中， 表示一个子序列。

换言之，$ G(x) $ 是对所有满足 $ f(S) = x $ 的 $ T $ 的非空子序列 $ S $，先计算每个 $ S $ 中元素之和的平方，再将这些平方值求和（模 $ 1,000,000,007 $），最后将该和乘以 $ x $ 所得的结果（此处最后的乘法不取模）。

你需要计算 $ G(0),,G(1),,\dots,,G(999,999) $。为减小输出规模，请输出值
，
其中 表示按位异或（XOR）运算符。

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.

第一行包含整数 $n$（$1 \leq n \leq 1\,000\,000$）——列表 $T$ 的大小。

下一行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（$0 \leq a_i \leq 999\,999$）——列表的元素。

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.

对于第一个样例，$ G $ 的非零值为 $ G(121) = 144,611,577 $、$ G(123) = 58,401,999 $、$ G(321) = 279,403,857 $、$ G(555) = 170,953,875 $。这些数的按位异或结果等于 $ 292,711,924 $。

例如，，因为子序列 $[123]$ 和 $[123,\,555]$ 代入函数 $ f $ 后的计算结果均为 $ 123 $。

对于第二个样例，我们有

对于最后一个样例，我们有 ，其中 是二项式系数。