A certain school rewards students for superior attendance and punctuality. The prize is received if there is no more than one lateness and no absence has lasted more than two consecutive days. If a student is late more than once in the specified duration of the award period or is absent three or more days in a row, the student is not eligible for a prize.

Note that multiple latenesses need not be on consecutive days to disentitle an award, but the three disqualifying absences need to be successive to cancel the award.

To keep track of attendance and punctuality for one student, a string of letters is used. For example:

PPPAAPAPPPAALAPPPPAP represents a sequence of Punctual days, Absence days and Lateness days that does qualify for the award, as none of the A's come in a group of three and there is only one lateness.

PPPAAPAPPPAAAPPPPAPL disqualifies the student because of the three absences in a row.

PPPAAPAPPPAALAPPPPAL disqualifies based on two latenesses.

A recent such prize period lasted 12 days. How many strings of 12 are there that would qualify for an award? There are obviously 3^12 possible strings altogether, many of which would not qualify; but how many do qualify?

---

Adapted from a Project Euler puzzle on-line.