The K factor of a string is defined as the number of times ‘abba’ appears as a substring.

Given two numbers N and k, find the number of strings of length N with ‘K factor’ = k.

● Do all calculations modulo 10^9+7

● Only lower case english alphabets are allowed.

● Overlapping matches should be counted as different substrings. For example:

The K factor of the string ‘abbabba’ is 2.

The K factor of the string ‘abbacdef’ is 1.

For example for N = 10 and k = 2, the number of length 10 strings with k factor 2 = 74357

strings (out of a possible 26^10 strings).

The solution has to be O(N^2).

Input:

3

4 1

7 1

10 2

1

70302

74357