The magical dragon Malygos has recently been saddened by the nerf to the Gadgetzan Auctioneer, so he came up with a math problem.
$S$ is a multiset, $S = {a_1, a_2, \ldots, a_n}$.
A subset $A = {a_{i_1}, \ldots, a_{i_m}}$ is chosen uniformly at random from $S$.
Compute the bitwise XOR $x$ of all elements in $A$, and find the expected value of $x^k$.
Input Format
The first line contains two positive integers $n$ and $k$.
The next $n$ lines each contain one integer, representing $a_i$.
Output Format
If the result is an integer, output it directly. If the result is a decimal (it is guaranteed to be a finite decimal), output its exact value (without trailing zeros).
Example
Input
4 2 0 1 2 3
Output
3.5
Constraints
$1 \le n \le 100000$, $1 \le k \le 5$, $a_i \ge 0$. The final answer is less than $2^{63}$. For $k = 1, 2, 3, 4, 5$, each accounts for 20% of the test data.