题目描述

Haibara有一个包含N个元素的集合S。

他想让你找出K个集合$S_1,S_2,...,S_k$（集合可以相等）。满足：

$S_i(1≤i≤k)是S的子集，且S_1∩S_2∩……∩S_k=∅$

现在请你告诉他满足条件的方案数。

输入描述

第一行两个整数N,K。

输出描述

输出一个数，即合法方案数。由于这个数可能知大，你只要输出这个数除以1000000007的余数。

样例

1 1

1

2 2

9

数据范围

30%的数据：1≤N,K≤10；

100%的数据：1≤N,K≤10^63-1。（注意是10^63-1，不是2^63-1）