C - 半分
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A_1, A_2, ..., A_N が与えられます。 この数列に以下の操作をちょうど K 回施します。
- 添字 i (1 \leq i \leq N) を一つ選ぶ。A_i を 2 で割る。ただし商は整数単位で計算し、あまりは切り捨てる。
K 回の操作のあとの数列としてありうるものの個数を 10^9 + 7 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 50
- 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
- 0 \leq K \leq 10^9
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
出力
答えを出力せよ。
入力例 1
3 2 0 3 4
出力例 1
6
はじめ、数列 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] となる。
入力例 2
3 100 1 1 1
出力例 2
7
入力例 3
5 7 10 12 15 20 30
出力例 3
330
入力例 4
7 1000000000 100261694256177806 55017793609323647 50568971510512136 98912633370372323 51937770757669401 50688484559490819 108712166294779912
出力例 4
322647718