We have N integers. The i-th integer is A_i.

Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

* When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

* 2 \leq N \leq 3 \times 10^5
* 0 \leq A_i < 2^{60}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

Examples

Input

3
1 2 3


Output

6


Input

10
3 1 4 1 5 9 2 6 5 3


Output

237


Input

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820


Output

103715602
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Washoum
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        inputClass in = new inputClass(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CXorSum4 solver = new CXorSum4();
        solver.solve(1, in, out);
        out.close();
    }

    static class CXorSum4 {
        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int[][] tab = new int[n][60];
            for (int i = 0; i < n; i++) {
                long x = sc.nextLong();
                String s = Long.toBinaryString(x);
                for (int j = 0; j < s.length(); j++) {
                    tab[i][59 - s.length() + 1 + j] = s.charAt(j) - '0';
                }
            }
            int[][] sum1 = new int[n][60];
            for (int i = 0; i < 60; i++) {
                sum1[n - 1][i] = tab[n - 1][i];
            }
            for (int i = n - 2; i >= 0; i--) {
                for (int j = 0; j < 60; j++) {
                    sum1[i][j] = sum1[i + 1][j] + tab[i][j];
                }
            }
            int[][] sum0 = new int[n][60];
            for (int i = 0; i < 60; i++) {
                sum0[n - 1][i] = 1 - tab[n - 1][i];
            }
            for (int i = n - 2; i >= 0; i--) {
                for (int j = 0; j < 60; j++) {
                    sum0[i][j] = sum0[i + 1][j] + 1 - tab[i][j];
                }
            }
            int mod = (int) 1e9 + 7;
            long[] pow = new long[60];
            pow[0] = 1;
            for (int i = 1; i < 60; i++) {
                pow[i] = (pow[i - 1] * 2) % mod;

            }
            long ans = 0;
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 60; j++) {
                    if (tab[i][j] == 1) {
                        ans += (sum0[i + 1][j] * pow[59 - j]) % mod;
                        ans %= mod;
                    } else {
                        ans += (sum1[i + 1][j] * pow[59 - j]);
                        ans %= mod;
                    }
                }
            }
            out.println(ans);
        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

