SRM 644 1 500 MakingTournament


Problem Statement

It has been decided that a big tournament-style programming contest is going to take place in the wolf country! Wolf Sothe is in charge of choosing the tournament bracket.

There are N competitors, numbered 1 through N. The tournament will have exactly K rounds. In each round, some of the competitors will drop out of the tournament and some will advance. The competitors who advance from round K are the winners of the tournament. A valid tournament must have at least one winner.

Each round of the tournament must look as follows.
  • At the beginning of the round, the competitors are divided into rooms. Each room must contain two or more competitors. The competitors in each room must have consecutive numbers.
  • In each room the competitors compete against each other. The best competitor in each room advances and all others drop out of the tournament.
  • After the round, the advancers are assigned new numbers 1 through R, where R is the number of rooms. A contestant with a smaller current number will always get a smaller new number.

For example, if there are N=6 competitors and K=2 rounds, there are 4 valid tournament brackets:


For the leftmost bracket shown above, the tournament would look as follows: In round 1 there would be two rooms: one with competitors {1,2,3,4} and the other with competitors {5,6}. After the round, the advancer from the first room would get a new number 1 and the advancer from the second room would get a new number 2. In round 2 there would be a single room containing those two competitors. The winner of that room would be the only winner of this tournament.

You are given the long N and the int K. Return the number of valid tournament brackets, modulo 1,000,000,007.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • N 6
    • K 2
    output
    Returns 4
    note
    Described in the statement.
  2. input
    • N 8
    • K 3
    output
    Returns 1
    note
    There is only one tournament with 8 competitors and 3 rounds.

  3. input
    • N 10
    • K 2
    output
    Returns 45
    note
    Note that in this test case some valid tournament brackets will have more than one winner.
  4. input
    • N 63
    • K 6
    output
    Returns 0
    note
    At least 64 competitors are required to make a valid tournament bracket with 6 rounds, so the answer is 0.
  5. input
    • N 1000000000000000
    • K 6
    output
    Returns 429388700

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.