题目描述
有一个长度为n的数字串，每个位置都是0或者1，并且要求不能出现连续的3个1。比如00110000101是满足条件的，但是00111100是不满足条件的。请你编写程序，求出满足条件的数字串数量，对10007取余数的结果。
【数据范围】
1 < n ≤ 100000。
输入
一个整数，表示数字串的长度n。
输出
一个整数，表示长度为n的合法数字串的数量，对10007取余数的结果。
样例输入
3样例输出
7
37