AMR12E - Dyslexic Gollum

'Light, light of Sun and Moon, he still feared and hated, and he always will, I think; but he was cunning. He found he could hide from daylight and moonshine, and make his way swiftly and softly by dead of night with his pale cold eyes, and catch small frightened or unwary things. He grew stronger and bolder with new food and new air. He found his way into Mirkwood, as one would expect.' - Gandalf, describing Gollum after he ventured forth from Moria.

Gollum has spent half a millennium in the long darkness of Moria, where his eyes grew used to the dark, and without caring for reading or writing, he became dyslexic. Indeed, as much as he hates the Moon and the Sun, he also hates strings with long palindromes in them.

Gollum has a tolerance level of K, which means that he can read a word so long as it does not contain any palindromic substring of length K or more. Given the values N and K, return how many BINARY strings of length N can Gollum tolerate reading.

Input

The first line contains T, the number of test cases.

Each test case consists of one line containing 2 integers, N and K.

Output

For each test case, output the answer modulo 1,000,000,007.

Constraints

1 <= T <= 100

1 <= N <= 400

1 <= K <= 10

Sample

Input:
3
2 2
3 3
3 4

Output:
2
4
8

Notes/Explanation of Sample

For the first test case, 01 and 10 are the valid binary strings, while 00 and 11 are invalid.

For the second test case, 001, 011, 100, 110 are the valid binary strings.

For the third test case, all possible binary strings of length 3 are valid.


Added by:Varun Jalan
Date:2012-12-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Varun Jalan - ICPC Asia regionals, Amritapuri 2012

hide comments
2015-09-07 10:03:04 paras meena
@Karan Ans will be 0.
2013-07-31 10:09:06 Karan Chauhan
What would be the answer to
1
3 2
be?
0 because reading the string is not possible now.
or
2, because 01 and 10 are the valid binary strings, if you see two digits.
4, because 01 and 10 are repeated twice in the 8 binary strings, that are valid from length 3??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.