Tom's girlfriend, Enigma, is a very mysterious person. When answering a question, she sometimes tell the truth
but sometimes don't. For example, "yes" might actually means "no", and "no" might actually means "yes". It could be very
dangerous to Tom if he didn't get the actual meaning.
Tonight, Tom want to ask his girlfriend whether she want to watch a movie or not.
Tom: "Enigma, would you like to watch a movie tonight?"
Enigma: "No."
Tom: "Was your last answer correct?"
Enigma: "Yes."
Tom: "Was your last answer correct?"
Enigma: "No."
....
Enigma always answered "no" to the first question which is actually meaningless.
Then Tom will ask n more "Was your last answer correct?" before he gets tired or... fired.
Fortunately, there is a way for Tom to get the true meaning of Enigma. He knows that although Enigma is
very strange, however, she still has a principle: At any moment, the number of times she lied will not be greater than
the number of times she said the truth plus k. Therefore, the number of strategy that Enigma can use is limited.
Note that the number of times she told a truth or a lie includes the answer of the first question.
Besides, Tom is very smart, Enigma is so afraid that he will understand her true meaning.
So Enigma turned to you, a nice man programmer, and begged for your help. She wanted to know how
many different strategies she can use to answer these n questions so that (1)Tom will be still confused whether
she want to see the movie or not. (2)Her principle is not violated.
The following example illustrate a strategy that would fail when n = 2 and k = 1
| watch a movie? | Was your last answer correct? | Was your last answer correct? | |
| Enigma's answer | no | yes | no |
| Possibility 1 | lie | lie | truth |
| Possibility 2 | truth | truth | lie |
Since in Possibility 1, at the moment when the first "Was your last answer correct?" is answered, Enigma has told 2 lies
while 0 truth is told. Therefore, Tom knows that Possibility 2 is the only possibility that Enigma really
don't want go to the movie. So, the strategy "yes, no" does not work for Engima.
However, as you can verify, "no, yes" works well in this case.
The input consists of many cases. In each case, two integers n, k (1<=n, k<=1000) are given
in a line, separated by a space. The number n indicates how many "Was your last answer correct?" will Tom ask
after he ask "Enigma, would you like to watch a movie tonight?". The number k is the maximum number of lies could be
more than truths told by Enigma at any moment.
For each case, output x % 100000007, where x is the number of strategies that Enigma
can use that (1)confuse Tom, (2)does not violate her principle.