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.