Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Team Work

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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

Output

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

Examples

Input

1 1

Output

1

Input

3 2

Output

24

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2024 15:10:14 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|