Your reliability service records one status for each student on each of n days. A record uses P for present, A for absent, or L for late. A record is rewardable when it contains at most one absence and never contains three consecutive late statuses.

Given n, return the number of rewardable records of length n, modulo 1,000,000,007.

Treat every day as a separate log entry. The order of statuses matters, and two records with different statuses on any day are different records.