問題
あなたはお金が無くなってしまったので$ \ N \ $体のスライムを討伐するというクエストを受けることにした。
各スライムにはぷよぷよ度というものがあり、$i \ (1 \leq i \leq N) \ $番目のスライムのぷよぷよ度は$ \ p_i \ $である。
スライムは自分のぷよぷよ度以上の威力の攻撃を受けるとやられてしまうが、自分のぷよぷよ度未満の威力の攻撃を受けるとスライムは二体のスライムに分裂する。
ぷよぷよ度が$ \ X \ $のスライムが分裂すると、分裂後のそれぞれのスライムのぷよぷよ度は$ \ \lbrack \frac{X}{2} \rbrack \ $となる。
あなたの攻撃力は$ \ P \ $であり、一回の攻撃で威力$ \ P \ $の攻撃をすることができる。
あなたがすべてのスライムを倒すのに必要な攻撃回数を$ \ 10^9 + 7 \ $で割った余りを出力せよ。
入力
$N \ P$ $p_1 \ p_2 \ \ldots \ p_N$
出力
全てのスライムを倒すのに必要な攻撃回数を$ \ 10^9 + 7 \ $で割った余りを出力せよ出力の末尾には改行を入れること。
制約
- $1 \leq N \leq 10^6$
- $1 \leq P \leq 10^{18}$
- $1 \leq p_i \leq 10^{18}$
- 入力は全て整数
入出力例
例１
入力
1 2 10
出力
7
例２
入力
5 5 100 50 80 30 1000
出力
651
例３
入力
1 1 1000000000
出力
73741816
$10^9+7 \ $で割った余りを出力することを忘れずに。