AT_code_festival_2018_quala_c 半分

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c 長さ $ N $ の整数列 $ A_1,\ A_2,\ ...,\ A_N $ が与えられます。 この数列に以下の操作をちょうど $ K $ 回施します。 - 添字 $ i $ ($ 1\ \leq\ i\ \leq\ N $) を一つ選ぶ。$ A_i $ を $ 2 $ で割る。ただし商は整数単位で計算し、あまりは切り捨てる。 $ K $ 回の操作のあとの数列としてありうるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 50 $ - $ 0\ \leq\ A_i\ \leq\ 10^{18} $ ($ 1\ \leq\ i\ \leq\ N $) - $ 0\ \leq\ K\ \leq\ 10^9 $ - 入力値はすべて整数である。 ### Sample Explanation 1 はじめ、数列 $ A $ は $ A\ =\ [0,\ 3,\ 4] $ です。 $ K\ =\ 2 $ 回の操作のあとの数列としてありうるものとしては、$ [0,\ 3,\ 4] $ や $ [0,\ 1,\ 2] $ などがあります。 数列 $ [0,\ 3,\ 4] $ は以下のようにして実現できます。 - $ i\ =\ 1 $ を選ぶ。数列は $ [0,\ 3,\ 4] $ となる。 - $ i\ =\ 1 $ を選ぶ。数列は $ [0,\ 3,\ 4] $ となる。 また、数列 $ [0,\ 1,\ 2] $ はたとえば以下のようにして実現できます。 - $ i\ =\ 2 $ を選ぶ。数列は $ [0,\ 1,\ 4] $ となる。 - $ i\ =\ 3 $ を選ぶ。数列は $ [0,\ 1,\ 2] $ となる。