http://acm.hdu.edu.cn/showproblem.php?pid=2842

配達式f(n)=2*f(n-2)+f(n-1)+1が見つかりました。
前のn個の輪を外したいなら、前のn-2個を外して、n番目の輪を外して、n-2個の輪を押して、n-1の輪を外します。
ACコード:

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 200907
using namespace std;
typedef long long L;
typedef struct str
{   
	L  s[3][3];
}Node;
Node a,b;
Node ceil(Node p,Node q)
{ Node c;
  memset(c.s,0,sizeof(c.s));
  for(int i=0;i<3;++i)
	  for(int j=0;j<3;++j)
		  for(int t=0;t<3;++t)
		    c.s[i][j]=(c.s[i][j]+p.s[i][t]*q.s[t][j])%M;
  return c;
}
Node doit(int k)
{ Node p=a,q=b;
   while(k)
   {  if(k&1) p=ceil(p,q);
       q=ceil(q,q);
	   k=k>>1;
   }
   return p;
}
int main()
{   int n;
	while(~scanf("%d",&n),n)
	{   
		 if(n==1) printf("1
");
	     else if(n==2) printf("2
");
	     else if(n>=3)
	    { 
			a.s[0][0]=1;a.s[0][1]=0;a.s[0][2]=0;a.s[1][0]=0;a.s[1][1]=1;a.s[1][2]=0;a.s[2][0]=0;a.s[2][1]=0;a.s[2][2]=1;
			b.s[0][0]=0;b.s[0][1]=2;b.s[0][2]=0;b.s[1][0]=1;b.s[1][1]=1;b.s[1][2]=0;b.s[2][0]=0;b.s[2][1]=1;b.s[2][2]=1;
			n-=2;
			Node c=doit(n);
			L k=(c.s[0][1]+c.s[1][1]*2+c.s[2][1])%M;
			printf("%I64d
",k);
       }
	}return 0;
}