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

$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\le n\le 100000$，$1\le k\le 5$，$a_i\ge 0$。最终答案小于 $2^{63}$ 。$k=1,2,3,4,5$ 各自占用 20% 的数据。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

来源

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

下载

样例数据下载