Problem: You are given an array s of n non-negative integers.

A 5-tuple of integers (a, b, c, d, e) is said to be valid if it satisfies the following conditions: 

  * 1 ≤ a, b, c, d, e ≤ n
  * (sa | sb) & sc & (sd ^ se) = 2i for some integer i
  * sa & sb = 0



Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of f(sa|sb) * f(sc) * f(sd^se) over all valid 5-tuples (a, b, c, d, e), where f(i) is the i-th Fibonnaci number (f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2)).

Since answer can be is huge output it modulo 109 + 7.

Input

The first line of input contains an integer n (1 ≤ n ≤ 106).

The second line of input contains n integers si (0 ≤ si < 217).

Output

Output the sum as described above, modulo 109 + 7

Examples

Input

2
1 2


Output

32


Input

3
7 4 1


Output

3520


Input

10
1 3 0 7 3 7 6 5 7 5


Output

1235424


Input

10
50 9 11 44 39 40 5 39 23 7


Output

113860062

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class sum_the_fibo
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static int maxn=(int)(1<<17);
	static long mod=(long)(1e9+7);
	static int invd=pow(maxn,mod-2);
	
	static int add(long a,long b)
	{
		long ret=a+b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int mul(long a,long b)
	{
		long ret=a*b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int pow(long a,long b)
	{
		long x=1,y=a;
		
		while(b>0)
		{	
			if(b%2==1)
			{
				x=mul(x,y)%mod;
			}
			
			y=mul(y,y);b=b/2;
		}
		
		return (int)x;
	}
	
	static void t_xor(int[] a,boolean inv)
	{
		int n=a.length; // compulsary power of 2 ...

		for(int len=2;len<=n;len*=2)
		{
			int half=len/2;
			
			for(int i=0;i<n;i+=len)
			{
				for(int j=0;j<half;j++)
				{
					int u=a[i+j],v=a[i+half+j];
					
					a[i+j]=add(u,v);
						
					a[i+j+half]=add(u,add(-v,mod));
				}
			}
		}
		
		if(inv)
		{
			for(int i=0;i<maxn;i++)
			{
				a[i]=mul(a[i],invd);
			}
		}
	}
	
	static void t_and(int[] a,boolean inv)
	{
		int n=a.length; // compulsary power of 2 ...

		for(int len=2;len<=n;len*=2)
		{
			int half=len/2;
			
			for(int i=0;i<n;i+=len)
			{
				for(int j=0;j<half;j++)
				{
					int u=a[i+j],v=a[i+half+j];
					
					if(!inv)
					{
						a[i+j]=v;
						
						a[i+j+half]=add(u,v);
					}
					
					else
					{
						a[i+j]=add(add(-u,mod),v);
						
						a[i+half+j]=u;
					}
				}
			}
		}
	}
	
	static void and_conv(int[] a,int[] b)
	{
		int n=a.length;// length of both is same, and is compulsary power of 2...
		
		t_and(a,false);t_and(b,false);
		
		for(int i=0;i<n;i++)
		{
			a[i]=mul(a[i],b[i]);
		}
		
		t_and(a,true);
	}
	
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt();int[] cnt=new int[maxn];
		
		int[] f=new int[maxn];f[1]=1;
		
		for(int i=2;i<maxn;i++)
		{
			f[i]=add(f[i-1],f[i-2]);
		}
		
		for(int i=0;i<n;i++)
		{
			int curr=sc.nextInt();cnt[curr]++;
		}
		
		int[] val1=new int[maxn];
		
		for(int i=0;i<maxn;i++)
		{
			for(int j=i;j>=0;j=(j-1)&i)
			{
				int now=i^j;
				
				int curr=mul(cnt[j],cnt[now]);
				
				val1[i]=add(val1[i],curr);
				
				if(j==0)
				{
					break;
				}
			}
		}
		
		int[] val2=new int[maxn];
		
		for(int i=0;i<maxn;i++)
		{
			val2[i]=cnt[i];
		}
		
		t_xor(val2,false);
		
		for(int i=0;i<maxn;i++)
		{
			val2[i]=mul(val2[i],val2[i]);
		}
		
		t_xor(val2,true);
		
		//out.println(Arrays.toString(val2));
		
		for(int i=0;i<maxn;i++)
		{
			val1[i]=(mul(val1[i],f[i]));
			
			val2[i]=(mul(val2[i],f[i]));
		}
		
		int[] val3=new int[maxn];
		
		for(int i=0;i<maxn;i++)
		{
			val3[i]=mul(cnt[i],f[i]);
		}
		
		and_conv(val1,val2);and_conv(val1,val3);
		
		int zz=0;
		
		for(int i=1;i<maxn;i++)
		{
			if(Integer.bitCount(i)==1)
			{
				zz=add(zz,val1[i]);
			}
		}
		
		out.println(zz);out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}