Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
Fence2
 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 337 Accepted: 138

Description

Having great success in painting the first fence, the workers were hired to paint the fence of one of the richest men in the town. Being satisfied with the sum offered to the entire team, the workers hadn't made caprices this time. They decided, however, to work in shifts: first the workers from the first shift, and then the ones from the second a.s.o. In each shift will work at least one and at most k workers. Also, each worker will work in exactly one shift. Surprised by the organization of the workers and being a lover of the counting problems, the owner of the fence wants to find out in how many ways the workers can be arranged in shifts. Because he announced that he will offer a great sum of money to the one that will give him the answer, you decided to write a program that will help you to win the first prize of the game.

Write a program that, for the values of N and K given, determinate how many possibilities to arrange the N workers in shifts exist, thus in each shift work at least one and at most K of them. Two arrangements are distinct if there exists one worker who works in shifts with different ordinal numbers.

Input

In the first line of the input there are two integers: N and K (1 <= K <= N <= 50), representing the total number of workers and the maximal number of workers that can work in the same shift.

Output

In the output you will write the determined number

Sample Input

`3 2`

Sample Output

`12`

Hint

For this sample the arrangements in shifts are:
 Possibility 1 Possibility 2 Possibility 3 Possibility 4 Possibility 5 Possibility 6 Shift1: 1 2 Shift1: 1 3 Shift1: 3 2 Shift1: 1 Shift1: 2 Shift1: 3 Shift2: 3 Shift2: 2 Shift2: 1 Shift2: 2 3 Shift2: 3 1 Shift2: 1 2 Possibility 7 Possibility 8 Possibility 9 Possibility 10 Possibility 11 Possibility 12 Shift1: 1 Shift1: 1 Shift1: 2 Shift1: 2 Shift1: 3 Shift1: 3 Shift2: 2 Shift2: 3 Shift2: 1 Shift2: 3 Shift2: 1 Shift2: 2 Shift3: 3 Shift3: 2 Shift3: 3 Shift3: 1 Shift3: 2 Shift3: 1

Source

[Submit]   [Go Back]   [Status]   [Discuss]