An attendance record for a student is represented as a string where each character denotes the attendance status for a single day:

• 'A': Absent.

• 'L': Late.

• 'P': Present.

A student is eligible for an attendance award if their record satisfies both of the following criteria:

• The student was absent strictly fewer than $2$ days (strictly fewer than $2$ 'A' characters in total).

• The student was never late for $3$ or more consecutive days (no substring of $3$ or more consecutive 'L' characters).

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an award. Since the answer may be very large, return it modulo $10^9 + 7$.

Constraints:

• $1 \leq$ n $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.