测试数据来自 Touhou/1013

题目描述

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

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

输入输出格式

输入格式

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

输出格式

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

样例

输入

6

输出

13

数据范围

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

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

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