## Vera and Sorting

View as PDF

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

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


A permutation is an ordered set of integers , consisting of distinct positive integers, each of which are at most . We will call the number the of the permutation.

You are given integers and .

Help Vera count the number of permutations of size such that steps() returns the value . This number could be large, so output it modulo .

• are integers

#### Input Specification

The input will be in the format:

#### Output Specification

Output one integer, the number of possible permutations, modulo .

#### Sample Input 1

3 5

#### Sample Output 1

2

#### Explanation of Sample Output 1

The 2 valid permutations are and .

#### Sample Input 2

5 29

#### Sample Output 2

0

#### Sample Input 3

20 100

#### Sample Output 3

262859528