魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心，于是他想了一道数学题。

$S$ 是一个可重集合，$S = \{a_1, a_2, \dots, a_n \}$。

等概率随机取 $S$ 的一个子集 $A = \{a_{i_1}, \dots, a_{i_m}\}$。

计算出 $A$ 中所有元素异或 $x$, 求 $x^k$ 的期望。

输入格式

第一行两个正整数 $n$, $k$。

以下 $n$ 行每行一个整数，表示 $a_i$。

输出格式

如果结果是整数，直接输出。如果结果是小数（显然这个小数是有限的），输出精确值（末尾不加多余的 $0$）。

样例一

input

4 2
0
1
2
3

output

3.5

限制与约定

$1 \leq n \leq 100000$，$1 \leq k \leq 5$，$a_i \geq 0$。最终答案小于 $2^{63}$ 。$k = 1,2,3,4,5$ 各自占用 20% 的数据。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 1 - By 毕克

下载

样例数据下载