/ WHOJ / 题库 /

集合

集合

描述

Doctor Who 有一个包含 \(N\) 个元素的集合 \(S\)。
她(\(13th\))想让你找出 \(K\) 个集合\(S_1,S_2,...,S_k\)(集合可以相等)。满足:
\(S_i(1≤i≤k)\)是 \(S\) 的子集,且\(S_1∩S_2∩……∩S_k=∅\)
现在请你告诉 Doctor Who 满足条件的方案数。

格式

输入格式

第一行为 \(N,K\)。

输出格式

输出一个数,即合法方案数。由于这个数可能很大,你只要输出这个数除以 \(1000000007\) 的余数。

样例1

输入样例1

2 2

输出样例1

9

样例解释

设包含\(2\)个元素的集合\(S\)为\({1,2}\),找出 \(2\)个 集合是\(S\)的子集,分别有:
{ }, { }
{1}, { }
{2}, { }
{1, 2},{ }
{ }, {1}
{ }, {2}
{ }, {1,2}
{1}, {2}
{2}, {1}
共\(9\)种方案,它们的交集都是空集。

限制

\(100\)%的数据,\(1≤N,K≤10^{63}-1\)。(注意是 10^{63}−1)