题目描述
如果一个长度为n的数字串，每个位置都是0或者1，并且把它向左移动两位之后，和原数字串不会有同一个位置上下都是1的情况，那么就把这个数字串称作合法的数字串。请你编写程序，求出长度为n的合法数字串的数量，对1000000007取余数的结果。
输入
一个整数，表示数字串的长度n。(1≤n≤10000)
输出
一个整数，表示长度为n的合法数字串的数量，对1000000007取余数的结果。
样例输入
3样例输出
6
36