Boxes and Stones

Time limit1sMemory limit128 MB

Summary
Count the initial distributions of S indistinguishable stones among the first B-1 boxes from which Carole, moving second each round, can force a win against Paul.
Level

Hard8 of 10

Topics
Game theory, Combinatorics, Dynamic programming, Prefix sum
Solved
No attempts yet

Problem

Paul and Carole play a game with SS stones and BB boxes numbered from 11 to BB. Before the game begins, the SS stones are distributed arbitrarily among boxes 11 through B−1B-1, leaving box BB empty. The game then proceeds in rounds.

In each round, Paul first chooses a subset PP of the stones currently in the boxes; he may take as many stones as he wants from as many boxes as he wants, or none at all, in which case PP is empty. Then Carole decides between two actions:

  • promote PP and discard the remaining stones, or
  • discard PP and promote the remaining stones.

To promote a stone means to move it to the box with the next number, so a stone in box bb moves to box b+1b+1. To discard a stone means to remove it from its box permanently, so it is not used in any later round.

Play continues until some stone reaches box BB, in which case Paul wins, or until no stones remain in the boxes, in which case Carole wins. Both players play optimally. Count the number of initial distributions of the SS stones among boxes 11 through B−1B-1 for which Carole can be certain of winning, even if Paul never makes a mistake.

Input

The input consists of several test cases, one per line, until end of file. Each line contains two integers SS and BB (1≤S≤2001 \le S \le 200, 2≤B≤1002 \le B \le 100), the number of stones and the number of boxes.

Output

For each test case, print on its own line the number of ways to distribute the SS stones among the first B−1B-1 boxes so that Carole is certain to win. Because this number can be very large, print it modulo 109+710^9 + 7.

Examples1

  1. Example 1

    Input
    2 3
    8 4
    42 42
    
    Expected output
    2
    0
    498467348