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