Integer Partitions into Exactly K Parts

Given two positive integers n and k, count the number of ways to partition n into exactly k positive parts. This problem asks you to compute the number of representations of n as a sum of k positive integers.

In mathematical terms, you are required to compute \(p_k(n)\), where the recurrence relation is given by:

\( dp[i][j] = dp[i-1][j-1] + dp[i-j][j] \) for \( i \ge j \), with the base case \( dp[0][0] = 1 \).

Note: If it is impossible to partition n into k parts (i.e. when k > n), the answer should be 0.

inputFormat

The input consists of two space-separated integers representing n (the integer to partition) and k (the number of parts). Read the input from standard input (stdin).

outputFormat

Output a single integer to standard output (stdout), which is the number of ways to partition n into exactly k positive parts.## sample

5 2

2