Migrated from Lutece 3255 派对

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

马上就是你的生日了，你打算举办一个生日派对。你向 $n$ 个朋友发送了派对邀请。但是恰逢期末，大家都很忙，你不确定他们会不会来。具体而言，每个人都有 $0.5$ 的概率来，或者不来。假若最后一共来了 $x$ 个人，那么你预计会花费 $x^k$ 的钱在这次派对上。$k$ 是一个一开始假定的数。你想知道举办这次派对的期望花费，于是开始了计算……

Input

一行，两个正整数，表示 $n$ 和 $k$。

Output

一行，一个整数，表示花费对 $10^9+7$ 取模的结果。

Samples

1 1

500000004

2 2

500000005

Constraints

$1\leq k\leq 5\times 10^3，1\leq n\leq 10^9$

Resources

2024 UESTC ICPC Training for Math