증가 부분수열

$1, 2, \ldots, N$ 으로 이루어진 수열 $p(1), p(2), \ldots, p(N)$ 에서 모든 원소가 서로 다르면 이 수열을 순열이라고 한다.

순열 $p$ 에 대하여 $1 \le i_1 < i_2 < \cdots < i_k \le N$ 인 인덱스가 존재하여 $p(i_1) < p(i_2) < \cdots < p(i_k)$ 를 만족하면, 순열 $p$ 는 길이 $k$ 인 증가 부분수열을 포함한다고 한다.

순열 $p$ 가 길이 $B$ 인 증가 부분수열은 포함하지만 길이 $B+1$ 인 증가 부분수열은 포함하지 않을 때, $B$ 를 이 순열의 증가 차수라고 한다.

정수 $N$ 이 주어졌을 때, 증가 차수가 정확히 $B$ 인 순열의 개수를 구하는 프로그램을 작성하여라. 개수가 매우 클 수 있으므로 $1{,}000{,}000{,}000$ 으로 나눈 나머지를 출력한다.

입력은 한 줄로 이루어진다. 이 줄에는 두 정수 $N$ 과 $B$ ($1 \le N \le 40$, $1 \le B \le 5$) 가 하나 이상의 공백으로 구분되어 주어진다.

증가 차수가 정확히 $B$ 인 순열의 개수를 $1{,}000{,}000{,}000$ 으로 나눈 나머지를 정수 하나로 출력한다.