Count Permutations with Exactly K Inversions

Given two integers N and K, consider all permutations of the set \(\{1,2,\dots,N\}\). A pair \((i,j)\) is called an inversion if \(i a_j\) for the permutation \(a_1,a_2,\dots,a_N\). The task is to count how many permutations have exactly \(K\) inversions. For example, when \(N=5\) and \(K=3\), there are exactly 15 such permutations:

• [1, 2, 5, 4, 3]
• [1, 3, 4, 5, 2]
• [1, 3, 5, 2, 4]
• [1, 4, 2, 5, 3]
• [1, 4, 3, 2, 5]
• [1, 5, 2, 3, 4]
• [2, 1, 4, 5, 3]
• [2, 1, 5, 3, 4]
• [2, 3, 1, 5, 4]
• [2, 3, 4, 1, 5]
• [2, 4, 1, 3, 5]
• [3, 1, 2, 5, 4]
• [3, 1, 4, 2, 5]
• [3, 2, 1, 4, 5]
• [4, 1, 2, 3, 5]

Your task is to output the number of permutations with exactly \(K\) inversions.

Note: An inversion pair is defined as \((i,j)\) such that \(i a_j\). All formulas are rendered in \(\LaTeX\) format.

inputFormat

The input consists of a single line containing two integers (N) and (K), separated by a space.

outputFormat

Output a single integer, the number of permutations of ({1,2,\dots,N}) that contain exactly (K) inversions.

sample

5 3

15