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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DVaryingKibibits solver = new DVaryingKibibits();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DVaryingKibibits {
        Modular mod = new Modular(1e9 + 7);
        int limit = (int) 1e6;
        int digit = 6;
        int[][] sum = new int[7][limit];
        int[][] cnt = new int[7][limit];
        int[][] prod = new int[7][limit];
        int[] occur = new int[limit];
        CachedPow pow = new CachedPow(2, mod);
        IntRadix radix = new IntRadix(10);
        int[] way = new int[limit];
        Debug debug = new Debug(true);

        public int cnt(int i, int j) {
            if (cnt[i][j] == -1) {
                if (i == digit) {
                    return (int) (cnt[i][j] = occur[j]);
                }
                cnt[i][j] = 0;
                int cur = radix.get(j, i);
                if (cur < 9) {
                    cnt[i][j] += cnt(i, (int) radix.set(j, i, cur + 1));
                }
                cnt[i][j] += cnt(i + 1, j);
                cnt[i][j] = mod.valueOf(cnt[i][j]);
            }
            return (int) cnt[i][j];
        }

        public int prod(int i, int j) {
            if (prod[i][j] == -1) {
                if (i == digit) {
                    int ans = mod.valueOf((long) (1 + occur[j]) * occur[j] / 2);
                    ans = mod.mul(ans, j);
                    ans = mod.mul(ans, j);
                    return prod[i][j] = ans;
                }
                prod[i][j] = 0;
                int sum = 0;
                int cur = radix.get(j, i);
                if (cur < 9) {
                    prod[i][j] = mod.plus(prod[i][j], prod(i, (int) radix.set(j, i, cur + 1)));
                    sum = mod.plus(sum, sum(i, (int) radix.set(j, i, cur + 1)));
                }
                prod[i][j] = mod.plus(prod[i][j], prod(i + 1, j));
                prod[i][j] = mod.plus(prod[i][j], mod.mul(sum, sum(i + 1, j)));
            }
            return prod[i][j];
        }

        public int sum(int i, int j) {
            if (sum[i][j] == -1) {
                if (i == digit) {
                    return sum[i][j] = mod.mul(occur[j], j);
                }
                sum[i][j] = 0;
                int cur = radix.get(j, i);
                if (cur < 9) {
                    sum[i][j] = mod.plus(sum[i][j], sum(i, (int) radix.set(j, i, cur + 1)));
                }
                sum[i][j] = mod.plus(sum[i][j], sum(i + 1, j));
            }
            return sum[i][j];
        }

        public int ie(int i, int j, int cnt) {
            if (i == digit) {
                if (cnt % 2 == 1) {
                    return mod.valueOf(-way[j]);
                }
                return way[j];
            }
            int cur = radix.get(j, i);
            int ans = ie(i + 1, j, cnt);
            if (cur < 9) {
                ans = mod.plus(ans, ie(i + 1, (int) radix.set(j, i, cur + 1), cnt + 1));
            }
            return ans;
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            long t1 = System.currentTimeMillis();

            int n = in.readInt();
            SequenceUtils.deepFill(sum, -1);
            SequenceUtils.deepFill(cnt, -1);
            SequenceUtils.deepFill(prod, -1);

            for (int i = 0; i < n; i++) {
                occur[in.readInt()]++;
            }

            long t2 = System.currentTimeMillis();
            for (int i = 0; i < limit; i++) {
                int c = cnt(0, i);
                int p = prod(0, i);
                if (c == 0) {
                    continue;
                }
                way[i] = mod.mul(p, pow.pow(c - 1));
            }

            long t3 = System.currentTimeMillis();
            //inclusion-exclusion
            int[] ie = new int[limit];
            for (int i = 0; i < limit; i++) {
                ie[i] = ie(0, i, 0);
            }
            long t4 = System.currentTimeMillis();

            long xor = 0;
            for (int i = 0; i < limit; i++) {
                long val = (long) i * ie[i];
                xor ^= val;
            }

            out.println(xor);
            debug.debug("init", t2 - t1);
            debug.debug("dp", t3 - t2);
            debug.debug("ie", t4 - t3);
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, long x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

    }

    static class IntegerList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public IntegerList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerList(IntegerList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        private void checkRange(int i) {
            if (i < 0 || i >= size) {
                throw new ArrayIndexOutOfBoundsException();
            }
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerList list) {
            addAll(list.data, 0, list.size);
        }

        public int tail() {
            checkRange(0);
            return data[size - 1];
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerList)) {
                return false;
            }
            IntegerList other = (IntegerList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerList clone() {
            IntegerList ans = new IntegerList();
            ans.addAll(this);
            return ans;
        }

    }

    static class CachedPow {
        private int[] first;
        private int[] second;
        private Modular mod;
        private Modular powMod;
        private static int step = 16;
        private static int limit = 1 << step;
        private static int mask = limit - 1;

        public CachedPow(int x, Modular mod) {
            this.mod = mod;
            this.powMod = mod.getModularForPowerComputation();
            first = new int[limit];
            second = new int[Integer.MAX_VALUE / limit + 1];
            first[0] = 1;
            for (int i = 1; i < first.length; i++) {
                first[i] = mod.mul(x, first[i - 1]);
            }
            second[0] = 1;
            int step = mod.mul(x, first[first.length - 1]);
            for (int i = 1; i < second.length; i++) {
                second[i] = mod.mul(second[i - 1], step);
            }
        }

        public int pow(int exp) {
            return mod.mul(first[exp & mask], second[exp >> step]);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Modular {
        int m;

        public Modular(int m) {
            this.m = m;
        }

        public Modular(long m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public Modular(double m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public int valueOf(int x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return x;
        }

        public int valueOf(long x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return (int) x;
        }

        public int mul(int x, int y) {
            return valueOf((long) x * y);
        }

        public int plus(int x, int y) {
            return valueOf(x + y);
        }

        public Modular getModularForPowerComputation() {
            return new Modular(m - 1);
        }

        public String toString() {
            return "mod " + m;
        }

    }

    static class IntRadix {
        private int[] pow;
        private int base;

        public IntRadix(int base) {
            if (base <= 1) {
                throw new IllegalArgumentException();
            }
            this.base = base;
            IntegerList ll = new IntegerList(32);
            ll.add(1);
            while (!DigitUtils.isMultiplicationOverflow(ll.tail(), base, Integer.MAX_VALUE)) {
                ll.add(ll.tail() * base);
            }
            pow = ll.toArray();
        }

        public int get(int x, int i) {
            return (x / pow[i] % base);
        }

        public int set(int x, int i, int val) {
            return x + (val - get(x, i)) * pow[i];
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static boolean isMultiplicationOverflow(long a, long b, long limit) {
            if (limit < 0) {
                limit = -limit;
            }
            if (a < 0) {
                a = -a;
            }
            if (b < 0) {
                b = -b;
            }
            if (a == 0 || b == 0) {
                return false;
            }
            //a * b > limit => a > limit / b
            return a > limit / b;
        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}