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
hide comments
kelaseek:
20150331 08:33:03
Last edit: 20150401 15:38:01 

Kevin Sebastian:
20141227 13:35:27
Last edit: 20141228 08:13:15 

Aditya Pande:
20141027 10:00:32
Is n(goat meat) + n(buffalo meat) <= k?


Anita P:
20141023 02:10:41
Help with any complex test cases? 

Jacob Plachta:
20141022 17:27:17
Thanks, that's more like it... 

Andy:
20141022 17:27:17
Updated the description:


Jacob Plachta:
20141022 17:27:17
From the samples, I assume that the total number of pieces must be *exactly* N, not at most N.

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