4347: Varying Kibibits
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：3
通过：3
题目描述
D. Varying Kibibits
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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:
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 1000000007, then multiplied by x. The last multiplication is not modded.
You would like to compute G(0),G(1),...,G(999999). To reduce the output size, print the value
, where 
denotes the bitwise XOR operator.
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 ba
se 10.
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 1000000007, then multiplied by x. The last multiplication is not modded. You would like to compute G(0),G(1),...,G(999999). To reduce the output size, print the value
, where denotes the bitwise XOR operator.
Input
The first line contains the integer n (1≤n≤1000000)− the size of list T. The next line contains n space-separated integers, a1,a2,...,an (0≤ai≤999999)− the elements of the list.
Output
Output a single integer, the answer to the problem.
Examples
Input
3
123 321 555
Output
292711924
Input
1
999999
Output
997992010006992
Input
10
1 1 1 1 1 1 1 1 1 1
Output
28160
Note
For the first sample, the nonzero values of G are G(121)=144611577, G(123)=58401999, G(321)=279403857, G(555)=170953875. The bitwise XOR of these numbers is equal to 292711924. 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. 输入样例 复制
输出样例 复制