You are given an integer n.
A string is considered good if it consists only of the characters 'a' and 'b', and one of the following holds:
s = s1 + s2, where s1 and s2 are non-empty good strings, and the last character of s1 is different from the first character of s2.Return the number of good strings of length n, modulo 109 + 7.
Here, + denotes string concatenation.
Example 1:
Input: n = 4
Output: 6
Explanation:
"aaab", "abbb", "baaa", "bbba", "abab", and "baba"."aaab" = "aaa" + "b". Both parts are good because each contains one distinct character and has odd length, and their characters at the boundary are different."ab" = "a" + "b" is good, so "abab" = "ab" + "ab" is good because the boundary characters are different.Example 2:
Input: n = 3
Output: 4
Explanation:
The good strings are "aaa", "bbb", "aba", and "bab". Thus, the answer is 4.
Example 3:
Input: n = 2
Output: 2
Explanation:
The good strings are "ab" and "ba". Thus, the answer is 2.
Constraints:
1 <= n <= 1015