Nastya 在新年收到了一份礼物——一个魔法衣柜。它很神奇,因为每个月末,其中的衣服数量都会增加一倍(即衣服数量会比月初增加一倍)。
不幸的是,在加倍之后,衣柜有 50% 的概率吃掉其中一件衣服(如果有的话)。除了一年中的最后一个之外,每个月都会发生这种情况。
Nastya 现在拥有 x 件衣服,因此她对一年内预计拥有的衣服数量感兴趣。 Nastya 住在 Byteland,因此一年持续 k + 1 个月。
Nastya 真的很忙,所以她希望你解决这个问题。毕竟你是程序员。另外,您应该找到对 109 + 7 取模的答案,因为很容易看出它始终是整数。
输入
唯一的一行包含两个整数 x 和 k (0 ≤ x, k ≤ 1018),其中 x 是衣服的初始数量,k + 1 是 Byteland 一年中的月份数。
输出
在唯一的一行中打印一个整数 - Nastya 一年后预计拥有的衣服数量模 109 + 7。
示例
输入 #1
2 0
输出 #1
4
输入 #2
2 1
输出 #2
7
输入 #3
3 2
输出 #3
21
注意
在第一个示例中,一年仅包含一个月,因此衣柜根本不吃裙子。
在第一个月后的第二个例子中,有 3 件衣服有 50% 的概率,4 件衣服有 50% 的概率。因此,到年底,有 50% 的概率有 6 件衣服,50% 的概率有 8 件衣服。这样这个测试的答案就是 (6 + 8) / 2 = 7。