小红的漂亮串（二）
题号：NC262033
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义“漂亮串”为：至少有两个"red"子串。例如"redcred"为漂亮串，但"reedred"则不是漂亮串。
小红想知道，长度为 n 的、仅包含小写字母的字符串中，共有多少种不同的漂亮串？

输入描述:

一个正整数 n，代表漂亮串的长度。

输出描述:

长度为 n 的，漂亮串的种类数。答案对  取模。
示例1

输入

复制 
6

输出

复制 
1

说明

仅有"redred"这一个漂亮串