Magical Dragon's Expected Power

The magical dragon, Marigoth, recently felt upset due to the nerf applied to the auctioneer in Gadgetzan, so he devised a mathematical puzzle.

Let \( S \) be a multiset defined as \( S = \{a_1, a_2, \dots, a_n\} \). An arbitrary subset \( A = \{a_{i_1}, a_{i_2}, \dots, a_{i_m}\} \) is chosen uniformly at random from \( S \) (each subset is equally likely). For every chosen subset \( A \) (including the empty set), compute the cumulative XOR of its elements which we denote as \( x \). Further, compute \( x^k \) and calculate its expected value over all subsets.

Your task is to compute the expected value \( E = \mathbb{E}[x^k] \) modulo \( 10^9+7 \), given the set elements and the exponent \( k \).

inputFormat

The first line contains two integers \( n \) and \( k \) (\( 1 \leq n \leq 10^5 \), \( 0 \leq k \leq 10^9 \)).

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \) (\( 0 \leq a_i < 2^{30} \)).

outputFormat

Output the expected value of \( x^k \) modulo \( 10^9+7 \). Since the answer can be expressed as a fraction \( \frac{P}{Q} \), print \( P \times Q^{-1} \) modulo \( 10^9+7 \), where \( Q^{-1} \) is the modular inverse of \( Q \) modulo \( 10^9+7 \). Note that the empty subset is allowed and its cumulative XOR is defined to be 0.

sample

3 2
1 2 3

3