## HK - Help Kejriwal

no tags

```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 ash() = 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 SpecificationFirst 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 SpecificationOutput 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.Constraint1<= t <=501 <= n <= 5000 <= m <= 10000 <= ai <= 1000000000
Sample Input2`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 = 1When f(4)=0 and g(4) = (value obtained after any of the 32 possible flips), h()=0.   ways = 32total ways = 1 + 32 = 33`
``` Garg Ankit: 2015-02-23 09:05:14 @author In the sample input, t must be equal to 2. Kindly correct. Re: Corrected. Thanks! Last edit: 2015-02-25 15:33:07