Increasing Subsequences

A sequence $p(1), p(2), \ldots, p(N)$ made up of the numbers $1, 2, \ldots, N$ is called a permutation if all of its elements are distinct.

A permutation $p$ is said to contain an increasing subsequence of length $k$ when there exist indices $1 \le i_1 < i_2 < \cdots < i_k \le N$ such that $p(i_1) < p(i_2) < \cdots < p(i_k)$.

When a permutation $p$ contains an increasing subsequence of length $B$ but does not contain one of length $B+1$, the number $B$ is called the degree of increase of that permutation.

Given a number $N$, write a program that counts the permutations whose degree of increase is exactly $B$. Because this count can be very large, output its remainder modulo $1{,}000{,}000{,}000$.

The input consists of a single line containing two integers $N$ and $B$ ($1 \le N \le 40$, $1 \le B \le 5$), separated by one or more spaces.

Output a single integer: the number of permutations whose degree of increase is exactly $B$, taken modulo $1{,}000{,}000{,}000$.