Team Work

给定 $ n,k $，求： $$ \sum_{i=1}^n\binom n i \times i^k $$ $ 1 \leq k \leq 5000,1 \leq n \leq 10^9 $

You have a team of $ N $ people. For a particular task, you can pick any non-empty subset of people. The cost of having $ x $ people for the task is $ x^{k} $ . Output the sum of costs over all non-empty subsets of people.

Only line of input contains two integers $ N $ $ (1<=N<=10^{9}) $ representing total number of people and $ k $ $ (1<=k<=5000) $ .

Output the sum of costs for all non empty subsets modulo $ 10^{9}+7 $ .

1 1

1

3 2

24

In the first example, there is only one non-empty subset $ {1} $ with cost $ 1^{1}=1 $ . In the second example, there are seven non-empty subsets. \- $ {1} $ with cost $ 1^{2}=1 $ \- $ {2} $ with cost $ 1^{2}=1 $ \- $ {1,2} $ with cost $ 2^{2}=4 $ \- $ {3} $ with cost $ 1^{2}=1 $ \- $ {1,3} $ with cost $ 2^{2}=4 $ \- $ {2,3} $ with cost $ 2^{2}=4 $ \- $ {1,2,3} $ with cost $ 3^{2}=9 $ The total cost is $ 1+1+4+1+4+4+9=24 $ .