eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Increasing subsequences

Increasing subsequences

Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB

A sequence p(1), p(2), …, p(N) consisting of numbers 1, 2, … , N is called a permutation if all elements in the sequence are different.

It is said that a permutation p contains increasing subsequence of k elements when there are numbers

1i_1 < i_2 < … < i_kN

such that

p(i_1) < p(i_2) < … < p(i_k).

When a permutation p contains an increasing subsequence consisting of B elements and does not contain an increasing subsequence consisting of B+1 elements then the number B is called the degree of increase of this permutation.

You need to write a program which being given a number N calculates the number of permutations whose degree of increase is B. Since the number of such permutations might be quite big, it is necessary to calculate its remainder of integer division by 1000000000.

Вхідні дані

The input file consists of one line. The line contains two integer numbers N and B (1N40, 1B5) separated by one or more spaces.

Вихідні дані

The output file contains one integer number which is the remainder of integer division by 1000000000 of the number of permutations whose degree of increase is B.

Приклад

Вхідні дані #1
3 2
Вихідні дані #1
4
Джерело ACM Programming Contest 2005, Minsk, October 2005