HK  Help Kejriwal
During college days of Mr. Kejriwal, he wanted to go out with a girl of CSE on Valentines Day. The girl being a geek decided to organize a coding contest to decide the person with whom she will go out(Yeah! That craze). There was only one question in the contest and it goes like this.
Given n numbers a1, a2 ,....., an. There are two probabilistic functions f(x) and g(x). f(x) returns 0 or 1 with equal probability. g(x)returns a number by toggling(flipping) any one bit of x with equal probability, where x is an unsigned integer(32 bit).
A function h() is defined as
h() = f(a1)*g(a1) + f(a2)*g(a2) + ...... + f(an)*g(an)
Find the total number of ways in which h() takes the value m. Since, this value can be very large give it modulo 1000000007. (See test case explanation in order to understand when two ways are considered different.)
Also, find the expected value of function h() rounded up to exactly 6 decimal places.
Mr. Kejriwal had very less interest in coding and thus was not good at it. Help him top the contest in order to get him a date for Valentines Day.
Input Specification
First line consists of number of test cases t.
First line of each test case contains two integers n and m in order.
Second line of each test case consists of n integers a1, a2 ,....., an.
Output Specification
Output consists of t lines.
Each line contains 2 space separated values. First value is the number of ways in which h() is equal to m, modulo 1000000007. Second value is the expected value of h() rounded up to exactly 6 decimal places.
Constraint
1<= t <=50
1 <= n <= 500
0 <= m <= 1000
0 <= ai <= 1000000000
Sample Input
2
2 3
1 2
1 0
4
Sample Output
66 134217729.375000
33 67108865.859375
Explanation for second test case:
Value of h() needed is zero.
When f(4)=1 and g(4)=0, h()=0. ways = 1
When f(4)=0 and g(4) = (value obtained after any of the 32 possible flips), h()=0. ways = 32
total ways = 1 + 32 = 33
hide comments
Garg Ankit:
20150223 09:05:14
@author In the sample input, t must be equal to 2. Kindly correct.

Added by:  Sanket Singhal 
Date:  20150218 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  Own Problem(DNCOnsite BIT Mesra) 