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 a , a ,....., a. 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(a )*g(a ) + f(a )*g(a ) + ...... + f(a )*g(a )
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.
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 a , a ,....., a
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.
1<= t <=50
1 <= n <= 500
0 <= m <= 1000
0 <= a<= 1000000000
@author In the sample input, t must be equal to 2. Kindly correct.