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