Problem: Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k. 

Jzzhu wonders, how many groups exists such that ai1 & ai2 & ... & aik = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (109 + 7). Operation x & y denotes bitwise AND operation of two numbers.

Input

The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

Output a single integer representing the number of required groups modulo 1000000007 (109 + 7).

Examples

Input

3
2 3 3


Output

0


Input

4
0 1 2 3


Output

10


Input

6
5 2 0 5 2 1


Output

53

Solution (in JAVA):

Solution:
						import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Stack;
								
									 
							public	    class Main implements Runnable
									{
										static final int MAX = 1000000007;
										static class InputReader
										{
											private InputStream stream;
											private byte[] buf = new byte[1024];
											private int curChar;
											private int numChars;
											private SpaceCharFilter filter;
											private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
									
											public InputReader(InputStream stream)
											{
												this.stream = stream;
											}
											
											public int read()
											{
												if (numChars==-1) 
													throw new InputMismatchException();
												
												if (curChar >= numChars)
												{
													curChar = 0;
													try 
													{
														numChars = stream.read(buf);
													}
													catch (IOException e)
													{
														throw new InputMismatchException();
													}
													
													if(numChars <= 0)				
														return -1;
												}
												return buf[curChar++];
											}
										 
											public String nextLine()
											{
												String str = "";
									            try
									            {
									                str = br.readLine();
									            }
									            catch (IOException e)
									            {
									                e.printStackTrace();
									            }
									            return str;
											}
											public int nextInt()
											{
												int c = read();
												
												while(isSpaceChar(c)) 
													c = read();
												
												int sgn = 1;
												
												if (c == '-') 
												{
													sgn = -1;
													c = read();
												}
												
												int res = 0;
												do 
												{
													if(c<'0'||c>'9') 
														throw new InputMismatchException();
													res *= 10;
													res += c - '0';
													c = read();
												}
												while (!isSpaceChar(c)); 
												
												return res * sgn;
											}
											
											public long nextLong() 
											{
												int c = read();
												while (isSpaceChar(c))
													c = read();
												int sgn = 1;
												if (c == '-') 
												{
													sgn = -1;
													c = read();
												}
												long res = 0;
												
												do 
												{
													if (c < '0' || c > '9')
														throw new InputMismatchException();
													res *= 10;
													res += c - '0';
													c = read();
												}
												while (!isSpaceChar(c));
													return res * sgn;
											}
											
											public double nextDouble() 
											{
												int c = read();
												while (isSpaceChar(c))
													c = read();
												int sgn = 1;
												if (c == '-') 
												{
													sgn = -1;
													c = read();
												}
												double res = 0;
												while (!isSpaceChar(c) && c != '.') 
												{
													if (c == 'e' || c == 'E')
														return res * Math.pow(10, nextInt());
													if (c < '0' || c > '9')
														throw new InputMismatchException();
													res *= 10;
													res += c - '0';
													c = read();
												}
												if (c == '.') 
												{
													c = read();
													double m = 1;
													while (!isSpaceChar(c)) 
													{
														if (c == 'e' || c == 'E')
															return res * Math.pow(10, nextInt());
														if (c < '0' || c > '9')
															throw new InputMismatchException();
														m /= 10;
														res += (c - '0') * m;
														c = read();
													}
												}
												return res * sgn;
											}
											
											public String readString() 
											{
												int c = read();
												while (isSpaceChar(c))
													c = read();
												StringBuilder res = new StringBuilder();
												do 
												{
													res.appendCodePoint(c);
													c = read();
												} 
												while (!isSpaceChar(c));
												
												return res.toString();
											}
										 
											public boolean isSpaceChar(int c) 
											{
												if (filter != null)
													return filter.isSpaceChar(c);
												return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
											}
										 
											public String next() 
											{
												return readString();
											}
											
											public interface SpaceCharFilter 
											{
												public boolean isSpaceChar(int ch);
											}
											public boolean ready(){
												try {
													return br.ready();
												} catch (IOException e) {
													return false;
												}
											}
										}
									 	
										public static void main(String args[]) throws Exception
										{
											new Thread(null, new Main(),"Main",1<<26).start();
										}
										int a;
										int b;
										final int bit = 20;
										public void run()
										{	
											InputReader sc= new InputReader(System.in);
											PrintWriter w= new PrintWriter(System.out);
											int n = sc.nextInt();
											int[] arr=  new int[(1<<(bit))];
											int[] inp = new int[n];
											for(int i = 0;i < n;i++){
												inp[i] = sc.nextInt();
												arr[inp[i]]++;
											}
											int[] ans = new int[(1<<bit)];
											for(int i = 0;i < (1<<bit);i++){
												ans[i] = arr[i];
											}
											for(int i = 0;i < bit;i++){
												for(int j = 0;j < (1<<bit);j++){
													if((j & (1<<i)) != 0){
														ans[j^(1<<i)] += ans[j];
													}
												}
											}
											fun();
											long an =  0;
											for(int i = 0;i < (1<<bit);i++){
												int nbits = Integer.bitCount(i);
												long add = pow[ans[i]] + MAX - 1;
												if(nbits % 2 == 0){
													an = (an + add)%MAX;
												}else{
													an = (an + MAX - add)%MAX;
												}
											}
											w.println(an);
											w.close();
										}
										long pow[] = new long[1000005];
										void fun(){
											pow[0] = 1;
											for(int i = 1;i < pow.length;i++){
												pow[i] = (pow[i-1] * 2)%MAX;
											}
										}
										long power(int n,int m){
											long res = 1;
											n = (n) % MAX;
											while(m > 0){
												if((m & 1) == 1){
													res = (res * n) %MAX;
												}
												m = m >> 1;
												n = (n * n) % MAX;
											}
											return res;
										}
										
										static class Pair implements Comparable<Pair>{
											double a;
											double b;
											
											Pair(double a,double b){
												this.a = a;
												this.b = b;
												
											}
											public boolean equals(Object o)
											{
												Pair p = (Pair)o;
												return (p.a==this.a && p.b== this.b);
											}
											public int compareTo(Pair p){
												return Double.compare(this.a,p.a);
											}
											public int hashCode()
											{
												return new Double(a).hashCode()*31 + new Double(b).hashCode()*17;
											}
										}
									}