稳定串(stable)
【问题描述】
给定一个长度为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解释】
000000、1110000、0111000、0011100、0001110、0000111、1110111这7个是满足要求的稳定串。
【样例输入3】
1718
【样例输出2】
2447
【数据规模与约束】
对于20%的数据,n≤100。
对于50%的数据,n≤10000。
对于100%的数据,n≤1000000。