题目描述

给定序列 $a_{1\cdots n}$，求它的子序列 $a_{p_1\cdots p_m}$ 的 $(\bigoplus_{i=1}^m a_{p_i})^k$ 的期望值，其中 $\bigoplus$ 是异或符号。

输入格式

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

接下来 $n$ 行，第 $i+1$ 行一个整数表示 $a_i$。

输出格式

若答案是整数，直接输出。

否则答案一定是一个有限小数，输出答案的精确值，末尾不添加额外的 $0$。

4 2
0
1
2
3

3.5

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq k\leq 5$，$a_i\ge 0$，最终答案小于 $2^{63}$。

对于 $k=1,2,3,4,5$，各自存在 $20\%$ 的数据。

来源

$2015$ 年国家集训队测试。