Given an array of first n natural numbers. Calculate number of total permutations with exactly k pairs satisfy the condition a[i]<a[j] and i<j.

Example — n = 3, k = 2

All permutations — [1,2,3][1,3,2][2,1,3][2,3,1][3,2,1][3,1,2]

Output — 2 ([2,1,3][1,3,2])