Counting Permutations with Specified Inversions

In this problem, an inversion in a permutation is defined as a pair of indices ( (i,j) ) such that ( i < j ) and ( a_i > a_j ). Given two integers ( n ) and ( k ), your task is to compute the number of permutations of the set ({1, 2, \ldots, n}) that have exactly ( k ) inversions. This can be computed using dynamic programming by defining ( dp[i][j] ) as the number of permutations of ({1,2,\ldots,i}) with exactly ( j ) inversions. The recurrence is given by: [ dp[i][j] = \sum_{x=0}^{\min(j, i-1)} dp[i-1][j-x] ] with the base case ( dp[0][0] = 1 ).

Example:
For ( n = 3 ) and ( k = 1 ), the expected output is 2.

inputFormat

The input is provided via stdin as a single line containing two space-separated integers: ( n ) (the number of elements in the permutation) and ( k ) (the specified number of inversions).

outputFormat

Output a single integer to stdout which represents the number of permutations of ( {1, 2, \ldots, n} ) with exactly ( k ) inversions.## sample

3 1

2