C. Настя и платяной шкаф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Новый Год Насте подарили волшебный платяной шкаф. Он волшебный, так как в конце каждого месяца количество платьев в нем удваивается (то есть платьев становится в два раза больше, чем в начале месяца).

К несчастью, сразу после удвоения, в каждый месяц года кроме последнего (на Новый Год шкаф, как и все люди в Байтландии, отдыхает), шкаф с вероятностью 50% съедает одно платье (конечно, если оно в нём есть).

Сейчас у Насти есть x платьев, и ей стало интересно, каково математическое ожидание количества платьев в шкафу через год. Настя живет в Байтландии, а в Байтландии год длится k + 1 месяц.

К сожалению, Настя сейчас очень занята, поэтому, так как вы программист, она попросила вас решить эту задачу. Ответ вы должны вывести по модулю 109 + 7, так как можно показать, что ответ всегда является целым числом.

Входные данные

В единственной строке вводятся два целых числа x и k (0 ≤ x, k ≤ 1018), где x — начальное количество платьев, а k + 1 — количество месяцев в году Байтландии.

Выходные данные

В единственной строке выведите одно число — математическое ожидание количества платьев у Насти через год по модулю 109 + 7.

Примеры
Входные данные
2 0
Выходные данные
4
Входные данные
2 1
Выходные данные
7
Входные данные
3 2
Выходные данные
21
Примечание

В первом тесте год в Байтландии длится один месяц, таким образом, шкаф никогда не ест платья.

Во втором тесте после первого месяца с вероятностью 50% в шкафу 3 платья, и с вероятностью 50% 4 платья. Тогда в конце года в шкафу с вероятностью 50% 6 платьев, и с вероятностью 50% 8 платьев. Таким образом, ответ на данный тест равен (6 + 8) / 2 = 7.