稳定串（stable）
【问题描述】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
例如长度为7的01串中，0000000、1110000、0111000、1110111都是稳定串，而1011100、1111000、1111110则都不是稳定串。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入格式】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一行一个整数n，表示01串的长度。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出格式】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
仅一行一个整数，表示长度为n的01串中稳定串的数量，由于数量可能很大，仅输出结果模10007的余数即可。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入1】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出1】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例1解释】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0000、1110、0111这3个是满足要求的稳定串。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入2】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出2】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例2解释】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
000000、1110000、0111000、0011100、0001110、0000111、1110111这7个是满足要求的稳定串。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入3】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1718Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出2】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2447Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据规模与约束】Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于20%的数据，n≤100。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于50%的数据，n≤10000。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于100%的数据，n≤1000000。Foz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
