题目描述

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

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

输入格式

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

输出格式

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

输入数据#1

4

输出数据#1

3

解释#1

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

输入数据#2

7

输出数据#2

7

解释#2

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

输入数据#3

1718

输出数据#3

2447

数据范围

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