You are given *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 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 

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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8758e4ee150415656efb78a88beae1c6d7f1c5bb.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/c4b7092c0f7ce6535f2574569c98f7b3c2fe2c5f.png" style="max-width: 100.0%;max-height: 100.0%;"/> 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, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 999 999) — the elements of the list.
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, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/53a1c46c7cd2d3d56e89fe99af6328601758b327.png" style="max-width: 100.0%;max-height: 100.0%;"/>, since the subsequences [123] and [123, 555] evaluate to 123 when plugged into *f*.

For the second sample, we have <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/330ab8a9387bb33a82877190f4439f4e9ccd8e92.png" style="max-width: 100.0%;max-height: 100.0%;"/>

For the last sample, we have <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/0e0eeb7662af22bf04ea1a2ea669b162d53ad7ba.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/4f42013cbab8c31325f2cf28b60aa2ccc1cf89d3.png" style="max-width: 100.0%;max-height: 100.0%;"/> is the binomial coefficient.
3
123 321 555
292711924
1
999999
997992010006992
10
1 1 1 1 1 1 1 1 1 1
28160
3
534185 663311 372491
1081839767962341
10
595436 647991 285857 373944 855766 551711 399789 673915 873668 415038
1076029205780999
import sys
readline=sys.stdin.readline

m=6
M=10**m
dp0=[0]*M
dp1=[0]*M
dp2=[0]*M
mod=10**9+7
N=int(readline())
A=list(map(int,readline().split()))
for a in A:
    dp0[a]+=1
    dp1[a]+=a
    dp2[a]+=a**2%mod
for i in range(m):
    for a in range(M-1,-1,-1):
        if a%(10**(i+1))<9*10**i:
            dp0[a]+=dp0[a+10**i]
            dp1[a]+=dp1[a+10**i]
            dp2[a]+=dp2[a+10**i]
            dp0[a]%=mod
            dp1[a]%=mod
            dp2[a]%=mod
inve2=(mod+1)//2
G=[(dp1[a]**2+dp2[a])%mod*pow(2,dp0[a])%mod*inve2%mod*inve2%mod for a in range(M)]
for i in range(m):
    for a in range(M):
        if a%(10**(i+1))<9*10**i:
            G[a]-=G[a+10**i]
            G[a]%=mod
ans=0
for x in range(M):
    ans^=x*G[x]
print(ans)