Sets

Input

The first line contains two integers (1\le n,k \le 10^9).

Output

It is necessary to output f([n],k). Since the answer may be too large, output it modulo 10^9+7.

Examples

Note

In the first example, the set with $1$ element $(\{1\})$ and k=1, so f(\{1\},1)=2 $(\{1\}$ and $\{\varnothing \})$.

In the second example, the set with $2$ elements $(\{1,2\})$ and k=2. f(\{1,2\},2)=f(\{1,2\},1)+f(\{1\},1)+ +f(\{2\},1)+f(\{\emptyset\},1)=4+2+2+1=9.

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that the evaluation is still in the testing phase.

1. ($5$ points): k=1;

2. ($5$ points): n\le 10, k\le 2;

3. ($10$ points): n\le 15, k\le 3;

4. ($80$ points): without additional constraints.