Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Increasing subsequences
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 242Accepted: 63

Description

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 1 ≤ i1 < i2 < … < ik ≤ N such that p(i1) < p(i2) < … < p(ik).

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 1 000 000 000.

Input

The input consists of one line. The line contains two integer numbers N and B (1 ≤ N ≤ 40, 1 ≤ B ≤ 5) separated by one or more spaces.

Output

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

Sample Input

3 2

Sample Output

4

Source

Northeastern Europe 2005, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator