Integer Partition into Exactly k Parts

In this problem, you are given two positive integers ( n ) and ( k ). Your task is to compute the number of ways to partition ( n ) into exactly ( k ) positive integers. A partition is a way of writing ( n ) as a sum of positive integers where the order does not matter. For example, if ( n = 5 ) and ( k = 2 ), the valid partitions are: ( 1+4 ) and ( 2+3 ); hence, the answer is 2.

We can solve this problem using dynamic programming. Let ( dp[j][i] ) denote the number of ways to partition ( i ) using exactly ( j ) parts. The recurrence relation is given by:

[ dp[j][i] = dp[j-1][i-1] + dp[j][i-j] \quad \text{for } i \geq j, ]

with the base case ( dp[0][0] = 1 ). You must read data from the standard input and output the results to the standard output.

inputFormat

The input consists of several test cases. Each test case is given on a new line and contains two integers ( n ) and ( k ) separated by a space. The input terminates with a line containing two zeros ("0 0"), which should not be processed.

outputFormat

For each test case, output a single line containing the number of ways to partition ( n ) into exactly ( k ) parts.## sample

5 2
6 3
0 0

2
3