Submit solution

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 .

#### Constraints

- 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`

## Comments