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 little 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

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

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.

Constraints

1 <= t <= 50

1 <= n <= 500

0 <= m <= 1000

0 <= a_i <= 1000000000

Sample

Input
2
2 3
1 2
1 0
4

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: 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