An attendance record has one character per day: A for absent, L for late, or P for present. A record qualifies for an award if it contains at most one A in total and never contains three consecutive L characters.
Return the number of qualifying records of length n, modulo 1000000007.
Example 1:
Input: n = 1
Output: 3Explanation: The one-day records A, L, and P all qualify, giving 3 records.
Example 2:
Input: n = 3
Output: 19Explanation: Of the 27 three-day records, 7 contain at least two absences and one more is LLL. The remaining 27 - 7 - 1 = 19 qualify.
Example 3:
Input: n = 4
Output: 43Explanation: There are 13 valid records without an absence. Placing the single A in positions 1 through 4 gives 7, 8, 8, and 7 more records respectively, for a total of 43.
Constraints:
1 <= n <= 100000