资深守护
题目链接： 酷町堂：7083
7083 稳定串
经验值：1600 时间限制：1000毫秒 内存限制：128MB
瑶海区2021年小学信息学竞赛试题
不许抄袭，一旦发现，直接清空经验！
题目描述 De**ion
给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？
例如长度为7的01串中，0000000，1110000，0111000，1110111都是稳定串，而1011100，1111000，1111110则都不是稳定串。
输入描述 Input De**ion
一行一个整数n，表示01串的长度
输出描述 Output De**ion
仅一行一个整数，表示长度为n的01串中稳定串的数量，由于数量可能很大，仅输出结果模10007的余数即可
样例输入 Sample Input
样例1：4
样例2：7
样例3：1718
样例输出 Sample Output
样例1：3
样例2：7
样例3：2447
数据范围及提示 Data Size & Hint
对于20%的数据，n<=100
对于50%的数据，n<=10000
对于100%的数据，n<=1000000
Wrong Answer:0分
一点思路都没有，哪位能提个思路QAQ
初级启示者
找规律：
n=1：1种（0）
n=2：1种（00）
n=3：2种（000, 111）
n=4：3种（0000,1110, 0111）
n=5：4种（00000,11100,01110,00111）
n=6：5种（000000,111000,011100,001110,000111）
n=7：7种（0000000,1110000,0111000,0011100,0001110,0000111,1110111）
很明显，f[i]=f[i-4]+f[i-1]
