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

题目描述

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

输入描述:

一个正整数 n，代表数组的长度。
1\leq n \leq 10^5

输出描述:

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

输入

复制 
3

输出

复制 
1

说明

仅有"red"这一个漂亮串
示例2

输入

复制 
4

输出

复制 
52