Multiple Subject Lessons

Time limit1sMemory limit512 MB

Summary

Count the multisets of colored positive integers that sum to n, where two solutions match when every value has the same count in every color.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Kate's school has introduced multiple subject lessons.

For the Math, Art and Sociology lesson in the seventh grade, the students have the following task. They are given an integer $n$ . Each student has a set of $k$ colored pencils, with the colors numbered from $1$ to $k$ . Each student takes a sheet of paper and writes one or several integers on it, so that their sum equals $n$ . Each integer is written with one of the pencils, so it has one of the $k$ possible colors.

The students must agree to do the task in such a way that no two students have the same solution. Two solutions are the same if for each integer $a$ and each color $i$ , the number of integers $a$ of color $i$ on the students' sheets is the same.

The Math teacher is sure that the students will be able to complete the task. However, she wants to know how many solutions there are, and whether there might not be enough for all the students to have different solutions. Help her find that out!

Input

The input contains two integers $n$ and $k$ ( $1 \le n, k \le 15$ ).

Output

Print one integer: the number of solutions to the task.

Hint

The following picture shows all possible ways to solve the task in the first sample test. Note that the order of integers written doesn't matter, only the number of integers written with each color.

Examples1

Example 1
Input
```
3 2
```
Expected output
```
10
```