题面
众所周知，一个硬币有两面，一面朝上，一面朝下。如果两个硬币同时朝上，或者同时朝下，我们说两个硬币的状态是相同的。如果现在有(n)个硬币排成一排，显然有(2^n)种不同的排法。如果存在超过两个连续硬币的状态相同，我们就说这个硬币序列是幸运的。那么这种幸运的硬币序列有多少种呢？（(1le nle 10^9)）
思路
总方案数为(2^n-)不合法情况数
不合法情况即至多只有两个连续相同的硬币
先考虑此时相邻硬币状态互不相同，即(0101)交替或(1010)交替，有两种情况
然后从互不相同这种状态延伸至至多只有两个连续相同数的状态
可以看作选中这个(01)序列中的某一些数字，将其连写两遍，每选中一个数字则序列总长度会加(1)
例如对于长度为(4)的序列(0101)，选中位置(1)与位置(4)，则会变为(001011)，序列长度变为(6)，且此时至多只有两个连续相同数
那么明显的，对于所有初始长度为(lceil frac n 2 ceil le length le n)的(01)序列或者(10)序列，均可以通过一定的变换使其变成长度为(n)的至多只有两个连续相同数字的序列
对于位置选取，可通过组合数选取
则总方案数为
[2^n-2 imessum_{i=lceilfrac n 2
ceil}^{n}C_i^{n-i}
]
注意到题目中(max n=10^9)，直接求取组合数方案不可行
但通过打表或者杨辉三角逆推的方法可以发现，(sum_{i=lceilfrac n 2 ceil}^{n}C_i^{n-i}=Fibonacci[n+1])
故可以借助矩阵快速幂来求出斐波那契数列的值
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=10007;
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
struct Fibonacci{
struct matrix{
ll n,m,i;
ll data[2][2];
void init(){
for(i=0;i<n;i++)
data[i][i]=1;
}
}a,A,ans;
matrix multi(matrix &a,matrix &b){
ll i,j,k;
matrix temp;
temp.n=a.n;
temp.m=b.m;
for(i=0;i<temp.n;i++){
for(j=0;j<temp.m;j++)
temp.data[i][j]=0;
}
for(i=0;i<a.n;i++){
for(k=0;k<a.m;k++){
if(a.data[i][k]>0){
for(j=0;j<b.m;j++)
temp.data[i][j]=(temp.data[i][j]+(a.data[i][k]*b.data[k][j])%mod)%mod;
}
}
}
return temp;
}
matrix fast_mod(matrix &a,ll n){
matrix ans;
ans.n=a.n;
ans.m=a.m;
memset(ans.data,0,sizeof(ans.data));
ans.init();
while(n>0){
if(n&1) ans=multi(ans,a);
a=multi(a,a);
n>>=1;
}
return ans;
}
ll fibo(ll n){
a.n=1;
a.m=2;
a.data[0][0]=1;
a.data[0][1]=1;
A.n=2;
A.m=2;
A.data[0][0]=0;
A.data[0][1]=1;
A.data[1][0]=1;
A.data[1][1]=1;
ans=fast_mod(A,n-1);
ans=multi(a,ans);
return ans.data[0][0];
}
}f;
void solve()
{
int n;
cin>>n;
cout<<(qpow(2,n)-2LL*f.fibo(n+1)%mod+mod)%mod<<'
';
}
int main()
{
closeSync;
//multiCase
{
solve();
}
return 0;
}