数学题目。
设数列a[ i ]表示第 i 个位置的正反情况。并以1表示向上，0表示向下。
从反面考虑，即求最长相连的同值ａ［］数不超过２时，（ａ）的个数，设之为ｐ［ｎ］；
假设ａ［１］＝ｘ，进行分类：
１） ａ［２］＝！ｘ；
有ｐ［ｎ－１］种序列。即对ａ［２］值的指派不会减少２到ｎ的子（ａ）个数。
乍看之下这是奇怪的，但仅仅需要认识到以下几点，结论便是显然的。
ａ．！ｘ的指派是两种而非一种。
ｂ．由于ａ［１］与ａ［２］指派不同，在问题的结果中间，任意的从２到ｎ的子（ａ），在本身合法的条件下，构成的（ａ）也合法。
２） ａ［２］＝ｘ；
那么，显然的，ａ［３］＝！ｘ；利用（１）中的结论，有ｐ［ｎ－２］种序列（ａ）。
那么ｐ［ｎ］＝ｐ［ｎ－１］＋ｐ［ｎ－２］；
另外ｐ［１］＝２，ｐ［２］＝４，故，根据ｐ［］的递推公式，形式上的拓展ｐ［］的定义，使ｐ［０］＝２，ｐ［－１］＝０；
那么显然的，ｐ［ｎ］＝２×ｆ［ｎ＋１］ （ｆ［ｎ］表示斐波那契数列）。
问题的解就是ａｎｓ＝２＾ｎ－２×ｆ［ｎ＋１］；（ｎ＞＝３）
ａｎｓ＝０（ｎ＜３）
另外，代码的##处利用费马小定理减小了数据规模，节省了时间。不过就本题而言，这个优化也许不是必要的。
#include<stdio.h>
#define M 10007
int numqpow(int a,int k)
{
int ans=1;
while(k)
{
if(k&1)ans*=a;
k>>=1;
a*=a;
ans%=M;
a%=M;
}
return ans;
}
struct mat
{
int x[3][3];
}m0;//step=2
mat mul(mat a,mat b)
{
mat c;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
c.x[i][j]=0;
for(int k=1;k<=2;k++)
{
c.x[i][j]+=a.x[i][k]*b.x[k][j];
c.x[i][j]%=M;
}
}
}
return c;
}
mat matqpow(mat a,int k)
{
mat c=a;
k--;
while(k)
{
if(k&1)c=mul(c,a);
k>>=1;
a=mul(a,a);
}
return c;
}
void init()
{
m0.x[1][1]=1;
m0.x[1][2]=1;
m0.x[2][1]=1;
m0.x[2][2]=0;
}
int fib(int n)
{
mat ans=matqpow(m0,n);
return ans.x[1][2];
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
if(n<3)
{
printf("0\n");
continue;
}
init();
int ans=0-2*fib(n+1);
//printf("%d\n",ans);
n%=(M-1);//##
ans+=numqpow(2,n);
while(ans<0)ans+=M;
ans%=M;
printf("%d\n",ans);
}
return 0;
}