問題文

$N$ 人の選手で構成されるチームが, ある問題を解く. 選手には $1,2,3,\dots ,N$ と番号がついており, 選手 $i$ のレーティングは $A_i$ である.
このチームは, 難易度 $x$ の問題を時間 $(A_{1}XORx)+(A_{2}XORx)+(A_{3}XORx)+\cdots +(A_{N}XORx)$ で解くことができる.
難易度は $0$ 以上 $2^K-1$ 以下の整数であることが分かっており, これが一様な乱数で選ばれると仮定したとき, チームがこの問題を解くのにかかる時間の平均 $\mu$ と標準偏差 $\sigma$ を求めるプログラムを作れ.
ただし, $\mu$ と $\sigma$ は整数にならないので, 代わりに $\mu 2^K$ と ${\sigma }^2{4}^K$ をそれぞれ $1,000,000,009$ で割ったあまりを出力しなさい.

入力

$N$ $K$
$A_1{A}_2{A}_3\cdots A_N$

$1$ 行目には、整数 $N$ と $K$ が空白区切りで与えられる.
$2$ 行目には、整数 $A_1,A_2,A_3,\dots ,A_N$ が空白区切りで与えられる.

出力

$1$ 行目には、$\mu 2^K$ を $1,000,000,009$ で割ったあまりを出力しなさい.
$2$ 行目には、${\sigma }^2{4}^K$ を $1,000,000,009$ で割ったあまりを出力しなさい.

制約

すべての入力データは以下の条件を満たす.

• $1\le N\le 100000$.
• $0\le K\le 60$.
• $0\le A_i\le 2^K-1(1\le i\le N)$.

サンプル

3 2
1 2 3

18
20

10 3
1 4 1 4 2 1 3 5 6 2

280
1280