题目描述

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是使用积木搭建一座大厦。幼儿园将为每个小朋友提供 $n$ 块积木，第 i 块积木的高度恰好为 i，要求小朋友将全部积木一块一块地竖直叠放起来搭建成一座大厦，最下面一块积木的高度必须为 $1$，且要求任意两块相邻积木的高度差的绝对值不能超过 $2$。

对于一个搭建好的大厦，我们用大厦所使用的积木的高度从下到上依次组成的序列来表示。例如， 1, 3, 4, 2 就表示一个使用了 4 块积木的大厦，从下到上，每块积木的高度依次为 1, 3, 4, 2。

小 M 是个聪明的小朋友，她很快想出了构建符合比赛要求的大厦的所有方案。

你知道她能搭建多少座不同的符合比赛要求的大厦吗？答案可能很大，你需要将其 mod 1,000,000,007 后输出。

输入格式

多组数据。

每组数据一行，包含一个整数 $n$。

输出格式

每组数据输出一行，包含一个整数，表示答案 mod 1,000,000,007 。

样例输入

4
1234567

样例1输出

4
579443866

样例解释

此处仅解释样例中第一组数据：

4 块积木，可能有以下 4 种搭建方案：

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

数据范围

20% 的数据：$1 ≤ n ≤ 20$。

100% 的数据：$1 ≤ n ≤ 10^7$。每个测试点不超过20组测试数据。