NPC2014C - Satay Skewer


In Schematics Country, there is a place called NPC Town. NPC Town has many restaurants, each with their own signature dishes. Of course, NPC Town becomes one of the most designated travel place for tourists. Joke is an adventurer that likes to try many kinds of food. One day, Joke wants to taste all food in NPC Town. Because Joke likes every restaurant's signature dish, time flies so fast that it's now the last day of Joke's visit to NPC Town. For his last visit, he decides to go to a restaurant that his friend recommended, the restaurant is called “SaAn” (Sate Andaru). SaAn serves satay with three types of meat: chicken, goat, and buffalo. The unique thing about SaAn is each Satay can contain multiple types of meat. Every customer can order a combination of satay. If SaAn can't fulfill the customer's order, then the customer don't have to pay.

Knowing that, of course Joke wants to eat for free. He conjures a set of condition that must be met for his satay:

  • The first and last piece of each satay must be chicken meat.
  • There can't be two consecutive goat meat pieces.
  • There can't be two consecutive buffalo meat pieces.
  • The maximum number of goat meat and buffalo meat in each satay is K.
  • The number of meat in each satay is N.

The number of satay that Joke order is the number of possible combination of the above condition. Since the number of satay can be overwhelming, Joke decides that he will modulo the number of satay by 1000000007.

Since Andaru doesn't want to give free food, he asks for your help to count the number of satay that must be served to Joke.

Input

First line contains a T, number of test case.

Each test case is a line containing N and K.

Output

Number of satay that must be served to Joke.

Sample Input

2
2 1
4 3

Sample Output

1
7

Constraint

  • 1 ≤ T ≤ 1000000
  • 0 ≤ N ≤ 1000
  • 0 ≤ K ≤ 100
http://en.wikipedia.org/wiki/Satay

hide comments
kelaseek: 2015-03-31 08:33:03

Last edit: 2015-04-01 15:38:01
Kevin Sebastian: 2014-12-27 13:35:27

Last edit: 2014-12-28 08:13:15
Aditya Pande: 2014-10-27 10:00:32

Is n(goat meat) + n(buffalo meat) <= k?
or n(goat meat)<=k and n(buffalo meat) <= k?

ANS: their sum <= k

Last edit: 2014-11-01 06:52:52
Anita P: 2014-10-23 02:10:41

Help with any complex test cases?

Jacob Plachta: 2014-10-22 17:27:17

Thanks, that's more like it...

Andy: 2014-10-22 17:27:17

Updated the description:
The maximum number of goat meat and buffalo meat in each satay is K.

Jacob Plachta: 2014-10-22 17:27:17

From the samples, I assume that the total number of pieces must be *exactly* N, not at most N.

There are also issues with the data - N can be 0. I don't even know what answer would be expected in such a case (0 or 1). However, I can't get accepted no matter what I try, so that should be fixed.

Andy: Yes it must be exactly N, updated now. For N=0, answer is 1. Sorry for inconvenience.

Last edit: 2014-10-22 09:28:56

Added by:Andy
Date:2014-10-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NPC Schematics 2014