Vera and Sorting

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
2017 Winter Waterloo Local ACM Contest, Problem D

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:
  return count + steps(lesser) + steps(greater)

A permutation P is an ordered set of integers P_1, P_2, \cdots, P_N, 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 10^9 + 7.


  • 1 \le N \le 30
  • 1 \le K \le 900
  • N,K are integers

Input Specification

The input will be in the format:


Output Specification

Output one integer, the number of possible permutations, modulo 10^9+7.

Sample Input 1

3 5

Sample Output 1


Explanation of Sample Output 1

The 2 valid permutations are 2, 1, 3 and 2, 3, 1.

Sample Input 2

5 29

Sample Output 2


Sample Input 3

20 100

Sample Output 3



There are no comments at the moment.