## AMR12E - Dyslexic Gollum

no tags

'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 (STDIN):
The first line contains T, the number of test cases.
Each test case consists of one line containing 2 integers, N and K.
Output (STDOUT):
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
Sample Output:
2
4
8
Notes/Explanation of Sample Input:
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.

'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 (STDIN):

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

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

Output (STDOUT):

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

Sample Output:

2

4

8

Notes/Explanation of Sample Input:

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.

hide comments
 paras meena: 2015-09-07 10:03:04 @Karan Ans will be 0. Karan Chauhan: 2013-07-31 10:09:06 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??

 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