Leetcode 552. Student Attendance Record II

Count the number of length-n strings over {A,P,L} with fewer than 2 'A's and no three consecutive 'L's, returning the result mod 1e9+7. The core challenge is to compute this efficiently for n up to 1e5 using DP or linear-recurrence/matrix-exponentiation techniques.