题目描述

给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？

例如长度为7的01串中，0000000、1110000、0111000、1110111都是稳定串，而1011100、1111000、1111110则都不是稳定串。

输入格式

一行一个整数n，表示01串的长度。

输出格式

仅一行一个整数，表示长度为n的01串中稳定串的数量，由于数量可能很大，仅输出结果模10007的余数即可。

样例

4

3

解释#1

0000、1110、0111这3个是满足要求的稳定串。

7

7

解释#2

000000、1110000、0111000、0011100、0001110、0000111、1110111这7个是满足要求的稳定串。

1718

2447

数据范围

对于$20\%$的数据，$n≤100$。 对于$50\%$的数据，$n≤10000$。 对于$100\%$的数据，$n≤1000000$。