You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

大明的妈妈买了一包 $n$ 个草莓, 他们打算今天就把草莓吃掉.

题目描述

他们规定了吃草莓的顺序, 大明先吃, 每次可以吃 $1 \sim 2$ 个草莓, 然后妈妈可以吃 $1$ 个, 他们现在想知道, 一共有多少种不同的吃草莓方案?

答案可能很大, 对 1000000007 求模.

数据格式

输入格式

第一行一个整数 $n$ , 表示草莓的数量

输出格式

输出吃草莓的方案数.

样例

5

4

样例1解释

• ${1, 1, 1, 1, 1}$
• ${2, 1, 1, 1}$
• ${1, 1, 2, 1}$
• ${2, 1, 2}$

10

16

数据范围

$1 \leq n \leq 10^6$