愉快的递推式
题号：NC25354
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

已知 。
对于 的任意 f(n), 都满足 , 求 f(n)。


输入描述:

一个n 。

输出描述:

输出一行表示f(n)，答案对1000000007 取模。
示例1

输入

复制 
3

输出

复制 
7
示例2

输入

复制 
4

输出

复制 
25
示例3

输入

复制 
1000000000000

输出

复制 
33033517

备注:

2022.1.12更新了数据，by@王清楚