시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 5 | 5 | 5 | 100.000% |
Vera is very smart and invented a new sorting algorithm. She coded the following Python function to count how many steps her algorithm takes.
def steps(array): if len(array) == 0: return 0 pivot = array[0] count = 0 lesser = [] greater = [] for element in array: ## looks at each element in the array count += 1 if element < pivot: lesser.append(element) ## e.g. [1,3].append(5) => [1,3,5] elif element > pivot: greater.append(element) return count + steps(lesser) + steps(greater)
A permutation P is an ordered set of integers P1, P2, · · · , PN , consisting of N distinct positive integers, each of which are at most N. We will call the number N the size of the permutation.
You are given integers N and K.
Help Vera count the number of permutations P of size N such that steps(P) returns the value K. This number could be large, so output it modulo 109 + 7.
The input will be in the format:
N K
Constraints:
Output one integer, the number of possible permutations, modulo 109 + 7.
3 5
2
5 29
0
20 100
262859528
For the first example, the 2 valid permutations are 2, 1, 3 and 2, 3, 1.