C. No Sweep
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As is a customary tradition of very hardworking, diligent, productive, and busy problemsetters, Thomas (and other members of the Teamscode problemsetting team) like to play rinbot after meetings.

In a game of rinbot, there are $$$n$$$ rounds and $$$k$$$ problemsetters playing along with Thomas. There is always exactly $$$1$$$ winner per round, and a game is considered a sweep if Thomas is the winner in every single round.

Waymo tells you the conditions of the game and wants to know how many ways different problemsetters can win each round such that Thomas does not get a sweep.

Input

The first line of input will contain two integers $$$n$$$ and $$$k$$$ denoting the number of rounds in a game and the number of problemsetters who are playing aside from Thomas respectively $$$(1 \leq n \leq 10, 1 \leq k \leq 4)$$$.

Output

Output one integer $$$W$$$, the number of ways in which problemsetters (including Thomas) can be assigned to win rounds so that Thomas does not get a sweep.

Examples
Input
2 1
Output
3
Input
10 3
Output
1048575
Note

Let's say the $$$1$$$ other problemsetter in the first sample is Waymo. The way games could turn out could be any of the following:

1. Thomas, Thomas

2. Thomas, Waymo

3. Waymo, Thomas

4. Waymo, Waymo

Only in the first scenario Thomas gets a sweep so $$$4 - 1 = 3$$$ is the number of ways a game could end without Thomas sweeping.

The $$$3$$$ problemsetters in the second sample are Waymo, Dustin, and James. Not quite sure how this would help you solve the problem, but good luck!

 —

Idea: 3366

Preparation: 3366

Occurrences: Novice 3