The rt factor of a string is defined as the number of times ‘abba’ is occurring in the given string as a substring. Given two integers length of string N and Rt factor find number of strings of length N containing ‘abba’ as their substring exactly Rt times.

Example

```
abbabb -- rt factor is 1.
abbabbabb -- rt factor is 2. Overlaps has to be considered.
```

Test case

Input

N = 10 and Rt = 2

output

74357

Note that string contains only lowercase english alphabet letters.(26 letters)

1<=N<=500

K can be anything.

Expected Time complexity --> O(N^2)

Can anyone please help me with the solution for this problem i am thinking it in terms of DP but didn’t got any lead .