题目描述

你的任务是计算通过掷骰子一次或多次来构造和为 $n$ 的方法数。每次掷骰子产生的结果在 $1$ 到 $6$ 之间。

例如，如果 $n = 3$，可能的方式有 $4$ 种：

• $1 + 1 + 1$
• $1 + 2$
• $2 + 1$
• $3$

输入格式

唯一的输入行包含一个整数 $n$，表示目标和。

输出格式

输出方法数对 $10^9 + 7$ 取模后的结果。

样例

3

4

数据范围

• $1 \le n \le 10^6$