#3057. 玛里苟斯

玛里苟斯

Description

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

S 是一个可重集合,S={a1,a2,…,an}。

等概率随机取 S 的一个子集 A={ai1,…,aim}。

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

Format

Input

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

以下 n 行每行一个整数,表示 ai。

Output

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

Samples

4 2
0
1
2
3
3.5

Limitation

限制与约定

1≤n≤100000,1≤k≤5,ai≥0。最终答案小于 2^63 。k=1,2,3,4,5 各自占用 20% 的数据