← 返回题目列表

Codeforces · 992/C

C. 娜斯佳和衣柜

中文机器翻译题面 查看原题

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。