eolymp
bolt
Try our new interface for solving problems
Məsələlər

Guess Number

Guess Number

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

My tech-lover son has been attracted by the exciting game "Guess Number". In this game, the player must find a hidden positive integer number by at most T guesses (or turns). The parameter T together with a health parameter H is determined at the beginning of the game. In each turn, the player must enter a number. If the number is equal to the hidden number, he wins provided that H0. If the number is bigger than the hidden number, H is decreased by 1 unit of health. Otherwise, H remains unchanged. When H becomes negative or T reaches 0, the player definitely loses. The player can see the remaining turns and units of health after each turn. Although the game seems to be constructive, but something makes me suspicious! my son always wins. He claims he has a searching algorithm to find the hidden number but. I can’t believe him as for the given H and T there must be a big number which is not guessable by any searching algorithm. To prove my son claim is wrong, I kindly ask you to help me find the smallest M for which at least a number from 1 through M as the hidden number can’t be guessed for the given T and H.

For example, there is not any algorithm for finding all positive integers not greater than M = 3 by 2 turns and 0 units of health.

Giriş verilənləri

There are multiple test cases. Each test case consists of one line containing two non-negative integers T and H (0T, H100). The input terminates with "0 0" which should not be processed.

Çıxış verilənləri

For each test case output M described above in one line. As M maybe too large, output it modulo 10^9+7.

Nümunə

Giriş verilənləri #1
3 0
3 1
0 0
Çıxış verilənləri #1
4
7
Mənbə 11th Iran Internet Programming Contest, 28 November, 2013 (7 Azar, 1392)