Employee Of The Year

Problem Statement

Employee Of The Year Problem Description A paper company runs an annual appreciation event, and this year it has added a new category: Employee of the Year . Eligibility is decided purely from an employee's attendance record over the last N days. The attendance record for N days is a string of length N. Each character is the status for one day: A - Absent L - Late P - Present A record makes an employee eligible for the nomination when both of the following hold: The record contains at most 1 A in total. Two or more absences disqualify. The record contains no run of 3 or more consecutive L characters. A run of 1 or 2 late days in a row is fine; 3 in a row is not. You are given the integer N . Count how many of the 3^N possible records of length N are eligible. The count can be enormous, so print it modulo 1000000007 (that is, 10^9 + 7 ). Input Format A single line containing one integer N - the number of days in the record. Output Format Print a single integer: the number of eligible at