Strange Functions

All submissions for this problem are available.
While playing with arrays, Ira came across this problem. You are given an array A[0..N1]. You are needed to compute 2 functions F and G. They are defined as follows.
 F[i] = A[i]^{2} +(∑ G[j])^{2} where (i&j) = j and j < i
You need to print the summation (∑ i × F[i] × G[i]) mod 10^{9}+7.
Note : Here & denotes bitwise and operator.Input
 First line contains the integer N.
 N integers follow on the second line denoting the array A[0..N1].
Output
Output one integer: the answer to the problem.Constraints
 1 ≤ N ≤ 6*10^{5}
 1 ≤ A[i] ≤ 10^{9}
Example
Input: 5 1 1 1 2 3 Output: 5866820
Explanation
F[0] = A[0]*A[0] = 1G[0] = F[0]*F[0] = 1*1= 1
F[1] = A[1]*A[1] + G[0]^{2} = 1 + 1^{2} = 2
G[1] = F[0]*F[0] + F[1]*F[1] = 1*1 + 2*2 = 5
F[2] = A[2]*A[2] + G[0]^{2} = 1 + ( 1)^{2} = 2
G[2] = F[0]*F[0] + F[2]*F[2] = 1*1 + 2*2= 5
F[3] = A[3]*A[3] + (G[0] + G[1] + G[2])^{2} = 4 + (1 + 5 + 5)^{2} = 125
G[3] = F[0]*F[0] + F[1]*F[1] + F[2]*F[2] + F[3]*F[3] = 1*1 + 2*2 + 2*2 + 125*125 = 15634
F[4] = A[4]*A[4] + G[0]^{2} = 9 + 1^{2} = 10
G[4] = F[0]*F[0] + F[4]*F[4] = 1*1 + 10*10 = 101
ans = 0*1*1 + 1*2*5 + 2*2*5 + 3*125*15634 + 4*10*101 = 5866820
Author:  usaxena95 
Tags  usaxena95 
Date Added:  27012016 
Time Limit:  1  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions