Nastya와 옷장

Nastya는 New Year에 마법의 옷장을 선물로 받았다. 이 옷장이 마법인 이유는 매달 말에 그 안의 드레스 수가 두 배가 되기 때문이다(즉, 드레스 수가 그달 초의 두 배가 된다).

안타깝게도 옷장은 드레스 수가 두 배가 된 직후, 드레스가 하나라도 있으면 50%의 확률로 그중 한 벌을 먹어 버린다. 이는 매년 마지막 달을 제외하고 매달 일어난다.

현재 Nastya는 드레스를 x벌 가지고 있으므로, 일 년 뒤 자신이 가지게 될 드레스의 기댓값이 궁금해졌다. Nastya는 Byteland에 살기 때문에, 그곳의 일 년은 k + 1개월이다.

Nastya는 매우 바쁘기 때문에 여러분이 이 문제를 풀어 주기를 바란다. 어쨌든 여러분은 프로그래머이기 때문이다. 또한 답은 항상 정수임을 쉽게 알 수 있으므로, 109 + 7로 나눈 나머지를 구해야 한다.

유일한 줄에 두 정수 x와 k (0 ≤ x, k ≤ 1018)가 주어진다. 여기서 x은 초기 드레스 수이고, k + 1은 Byteland의 일 년을 이루는 개월 수이다.

유일한 줄에 일 년 뒤 Nastya가 가지게 될 드레스 수의 기댓값을 109 + 7로 나눈 나머지를 나타내는 하나의 정수를 출력한다.

첫 번째 예제에서 일 년은 단 한 달로 이루어지므로, 옷장은 드레스를 전혀 먹지 않는다.

두 번째 예제에서는 첫 달이 지난 뒤 50%의 확률로 드레스가 3벌이고, 50%의 확률로 4벌이다. 따라서 연말에는 50%의 확률로 드레스가 6벌이고, 50%의 확률로 8벌이다. 그러므로 이 테스트의 답은 (6 + 8) / 2 = 7이다.