На Новый Год Насте подарили волшебный платяной шкаф. Он волшебный, так как в конце каждого месяца количество платьев в нем удваивается (то есть платьев становится в два раза больше, чем в начале месяца).
К несчастью, сразу после удвоения, в каждый месяц года кроме последнего (на Новый Год шкаф, как и все люди в Байтландии, отдыхает), шкаф с вероятностью 50% съедает одно платье (конечно, если оно в нём есть).
Сейчас у Насти есть x платьев, и ей стало интересно, каково математическое ожидание количества платьев в шкафу через год. Настя живет в Байтландии, а в Байтландии год длится k + 1 месяц.
К сожалению, Настя сейчас очень занята, поэтому, так как вы программист, она попросила вас решить эту задачу. Ответ вы должны вывести по модулю 109 + 7, так как можно показать, что ответ всегда является целым числом.
Примечание
В первом тесте год в Байтландии длится один месяц, таким образом, шкаф никогда не ест платья.
Во втором тесте после первого месяца с вероятностью 50% в шкафу 3 платья, и с вероятностью 50% 4 платья. Тогда в конце года в шкафу с вероятностью 50% 6 платьев, и с вероятностью 50% 8 платьев. Таким образом, ответ на данный тест равен (6 + 8) / 2 = 7.