测试数据来自 Touhou/1013

题目描述

肥波纳气数列（\(\text{Fibonacci sequence}\)），又称答辩分割数列，因数学家莱昂纳多·肥波纳气（\(\text{Leonardo Fibonacci}\)）以肥波繁殖为例子而引入，故又称“肥波数列”，其数值为：\(1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193 \dots\)，在数学上，这一数列以如下递推的方法定义：\(F(1) = 1, F(2) = 1, F(3) = 1, F(n+1) = F(n) + F(n - 1) + F(n - 2)(n \geq 3，n \in N^*）\)。

现在，给与一个正整数 \(n\)，请你求出 \(F(n)\) 的值。

输入输出格式

输入格式

一行一个整数 \(n\)。

输出格式

一行一个数，表示答案模 \(10^9 + 7\) 的结果。

样例

输入

6

输出

9

数据范围

对于 \(30 \%\) 的数据，\(0 \leq n \leq 30\)；

对于 \(60 \%\) 的数据，\(0 \leq n \leq 10^7\)；

对于 \(100 \%\) 的数据，\(0 \leq n \leq 10^9\)。