题目描述

若一个长度为$n$的字符串，每个位置都是$0$或者$1$，并且要求不存在连续的$3$个及以上个$1$。比如$00110000101$是满足条件的，但是$00111100$是不满足条件的。请你编写程序，求出满足条件的数字串数量，对$10007$取余数的结果。

输入格式

一个正整数$n(2<=n<=10000)$，表示数字串的长度。

输出格式

一个正整数，表示满足条件的数字串数量，对$10007$取余数的结果。

输入样例1

3

输出样例1

7

输入样例2

5

输出样例2

24