07417. 出勤记录·计数 未做

记录一串长度为 $n$ 的出勤串，每位是 $\text{P}$（出勤）、$\text{L}$（迟到）、$\text{A}$（旷课）之一。合法的记录要求：旷课至多 1 次，且不能连续迟到 3 天或更多。合法的记录共有多少条？答案对 $10^9+7$ 取模。

一行一个整数 $n$。

一行一个整数：合法记录数 mod $10^9+7$。

$1\le n\le 100000$。