Description

扔 n 次硬币的结果可以用一串 0/1 序列来表示。给定 n，请统计有多少种扔硬币的结果中不含三个连续的 0 且不含三个连续的 1。 当 n 较大的时候，答案可能很大，所以输出答案模 1,000,000,007的余数即可。

Format

Input

单个整数：表示 n。

Output

单个整数：表示答案模 1,000,000,007 的余数。

Samples

3

6

Limitation

对于 30% 的数据，1≤n≤20； 对于 60% 的数据，1≤n≤5000； 对于 100% 的数据，1≤n≤1,000,000。