>>301
もう少し簡略化した漸化式
最後の3桁を**0、*01、011、111(*は0でも1でも良い)に分類して
a[n+1,**0]=a[n,**0]+a[n,*01]+a[n,111]
a[n+1,*01]=a[n,**0]
a[n+1,011]=a[n,*01]
a[n+1,111]=a[n,011]+a[n,111]