Problem: 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: 

  * 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 

<image> Here, <image> 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 <image>, where <image> 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, a1, a2, ..., an (0 ≤ ai ≤ 999 999) — 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) = 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, <image>, since the subsequences [123] and [123, 555] evaluate to 123 when plugged into f.

For the second sample, we have <image>

For the last sample, we have <image>, where <image> is the binomial coefficient.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000 + 7;
const int M = 1000000;
const int N = 1000007;
struct num {
  int d[6];
  int n;
  void init(int x) {
    n = x;
    memset(d, 0, sizeof d);
    int ptr = 5;
    while (x) {
      d[ptr] = x % 10;
      x /= 10;
      --ptr;
    }
  }
  num(int n = 0) : n(n) { init(n); }
  bool operator<(const num &o) const {
    for (int i = 0; i < (int)(6); ++i) {
      if (d[i] > o.d[i]) return false;
    }
    return true;
  }
  int get_cmpmask(const num &o) const {
    int mask = 0;
    for (int i = 0; i < (int)(6); ++i) {
      if (d[i] == o.d[i]) mask |= (1 << i);
    }
    return mask;
  }
  void print() {
    for (int i = 0; i < (int)(6); ++i) cerr << d[i];
    cerr << endl;
  }
} a[N];
int n;
int pw[N];
int firstbit[64];
int bcnt[64];
int pw10[6];
int dpcnt[N];
int dpsum[N];
int dpsum2[N];
int suff[N], G[N];
inline long long add(long long a, long long b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline long long sub(long long a, long long b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
void precalc() {
  for (int mask = 0; mask < (int)(64); ++mask) {
    firstbit[mask] = -1;
    bcnt[mask] = 0;
    for (int i = 0; i < (int)(6); ++i) {
      if (((mask >> i) & 1) == 0) {
        firstbit[mask] = i;
        break;
      }
    }
    for (int i = 0; i < (int)(6); ++i) {
      if ((mask >> i) & 1) ++bcnt[mask];
    }
  }
  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = add(pw[i - 1], pw[i - 1]);
  }
  pw10[5] = 1;
  for (int i = 4; i >= 0; --i) {
    pw10[i] = 10 * pw10[i + 1];
  }
}
void solve() {
  precalc();
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) {
    int t;
    scanf("%d", &t);
    dpcnt[t]++;
    dpsum[t] = add(dpsum[t], t);
    dpsum2[t] = add(dpsum2[t], (long long)t * t % MOD);
    a[i] = num(t);
  }
  for (int x = M - 1; x >= 0; --x) {
    num nx(x);
    for (int mask = 0; mask < (int)(64); ++mask) {
      if (mask == 0) continue;
      bool ok = true;
      int tx = x;
      for (int b = 0; b < (int)(6); ++b) {
        if ((mask >> b) & 1) {
          if (nx.d[b] == 9) {
            ok = false;
            break;
          }
          tx += pw10[b];
        }
      }
      if (!ok) continue;
      if (bcnt[mask] & 1) {
        dpcnt[x] = add(dpcnt[x], dpcnt[tx]);
        dpsum[x] = add(dpsum[x], dpsum[tx]);
        dpsum2[x] = add(dpsum2[x], dpsum2[tx]);
      } else {
        dpcnt[x] = sub(dpcnt[x], dpcnt[tx]);
        dpsum[x] = sub(dpsum[x], dpsum[tx]);
        dpsum2[x] = sub(dpsum2[x], dpsum2[tx]);
      }
    }
  }
  for (int ix = 0; ix < (int)(M); ++ix) {
    num x(ix);
    long long cur = 0;
    int cnt = dpcnt[ix];
    long long sum = dpsum[ix];
    long long sum2 = dpsum2[ix];
    long long impact = 0;
    if (cnt == 1)
      impact = sum2;
    else if (cnt >= 2) {
      impact = pw[cnt - 2] * (sum2 + sum * sum % MOD) % MOD;
    }
    suff[ix] = impact;
  }
  long long ans = 0;
  for (int x = M - 1; x >= 0; --x) {
    num nx(x);
    for (int mask = 0; mask < (int)(64); ++mask) {
      bool ok = true;
      int tx = x;
      for (int b = 0; b < (int)(6); ++b) {
        if ((mask >> b) & 1) {
          if (nx.d[b] == 9) {
            ok = false;
            break;
          }
          tx += pw10[b];
        }
      }
      if (!ok) continue;
      if (bcnt[mask] & 1)
        G[x] = sub(G[x], suff[tx]);
      else
        G[x] = add(G[x], suff[tx]);
    }
    ans ^= (long long)x * G[x];
  }
  cout << ans << endl;
}
void testgen() {
  FILE *f = fopen("input.txt", "w");
  fclose(f);
}
int main(int argc, char *argv[]) {
  solve();
  return 0;
}