## COCI '23 Contest 1 #4 Kocke

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

For his thirteenth birthday, Donald's parents bought him a brand-new set of Lego cubes. In the set, there are cubes of equal size, where the -th cube has color . Using these cubes he decided to build a wall.

Donald will build his wall on a row-like Lego base that has places where cubes can be put in. He puts the cubes in the following way:

• First, he puts the cube with color on an arbitrary spot on the base.
• For each cube from to , he places it in a spot neighboring the previously placed cube. If that spot isn't empty, he puts the new cube on top of all the others.

After he built the wall, Donald wrote on a piece of paper a sequence of length : in the -th position in the sequence he wrote the color of the top cube in the -th place, or if there isn't a cube in that place.

He immediately asked himself how many different sequences could he have written on the piece of paper. Two sequences are considered different if there exists a position in which they differ. After some time, he has managed to calculate the solution, but he is not sure whether it is correct, so he asks for your help.

#### Input Specification

The only line has integers and , the number of cubes, and the length of the base.

#### Output

In the only line, print the answer to Donald's question, modulo .

1 20
2 30
3 30

#### Sample Input 1

4 3

#### Sample Output 1

8

#### Explanation for Sample 1

All possible sequences are: .

#### Sample Input 2

3 5

#### Sample Output 2

14

#### Sample Input 3

100 200

#### Sample Output 3

410783331