SP22774 HK - Help Kejriwal

在大学时期，Kejriwal 先生渴望在情人节与一位计算机科学系的女生约会。这位女生极具个性，她决定以编程比赛的方式来选择约会对象（是的，她就是这么喜欢挑战）。比赛中只有一道题目，内容如下： 给定 $n$ 个数 $a_1, a_2, \ldots, a_n$。有两个概率函数 $f(x)$ 和 $g(x)$。函数 $f(x)$ 会以相等的概率返回 0 或 1。函数 $g(x)$ 会以相等的概率翻转 $x$ 的任意一位，其中 $x$ 是一个32位的无符号整数。 定义函数 $h()$ 为： $$ h() = f(a_1) \cdot g(a_1) + f(a_2) \cdot g(a_2) + \cdots + f(a_n) \cdot g(a_n) $$ 请计算 $h()$ 等于 $m$ 的方案总数。因为这个值可能非常大，请输出它对 $1000000007$ 取模后的结果。（可以参考样例解释，理解方案的不同定义。）同时，还要计算 $h()$ 的期望值，并精确到小数点后6位。 Kejriwal 先生对编程不太感兴趣，也并不擅长。请帮助他在比赛中胜出，从而实现他在情人节的约会愿望。

第一行是整数 $t$，表示有 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $m$。 接下来的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出 $t$ 行结果，每行对应一组测试数据。 每行结果包含两个数字，中间用空格隔开。第一个数字是 $h()$ 等于 $m$ 的方案总数，对 $1000000007$ 取模后的结果。第二个数字是 $h()$ 的期望值，精确到小数点后6位。

- $1 \le t \le 50$ - $1 \le n \le 500$ - $0 \le m \le 1000$ - $0 \le a_i \le 1000000000$ ## 样例输入 ``` 2 2 3 1 2 1 0 4 ``` ## 样例输出 ``` 66 134217729.375000 33 67108865.859375 ``` **本翻译由 AI 自动生成**