【题目描述】

你有一根长度为 $n$ 的木棍和一个神秘数字 $k$，你可以把他切成任意多段，要求每段的长度是正整数。一段长度为 $x$ 的贡献是 $x^k$，一种切割方案的权值是每段的权值积。

求所有 $2^{n-1}$ 种切割方案的权值和。

【输入格式】

输入一行两个整数 $n,k$。

【输出格式】

输出一行表示答案对 $10^9+7$ 取模的结果。

【样例输入1】

4 2

【样例输出1】

63

【样例输入2】

10 10

【样例输出2】

279205858

【数据范围与提示】

对于 $30\%$ 的数据，$n\le 1000$，$k\le 20$。

对于 $100\%$ 的数据，$n\leq 10^5$，$k\leq 20$。