140. 可爱串
内存限制：256 MB
时间限制：1.000 S
题目描述
我们定义子序列为字符串中可以不连续的一段，而子串则必须连续。例如 rderd 包含子序列 "red”，且不包含子串"red”，因此该字符串为可爱串。
小红想知道，长度为 n（3 <= n <= 10 ^ 5）的、仅由 'r''e''d' 三种字母组成的字符串中，有多少是可爱串? 答案请对 10 ^ 9 + 7 取模。
输入
输入共一行，包含一个正整数 n
输出
输出一个正整数，代表可爱串的数量
样例输入 复制
4样例输出 复制
3提示
"reed"、"rerd"、"rded"