题目链接：https://codeforces.com/contest/15/problem/E
什么时候才能推出这么优雅的公式啊QAQ
#include <iostream>
using namespace std;
static const int MAXN=1e6+10;
static const int MOD=1e9+9;
int a[MAXN],b[MAXN];
int ans;
int main()
{
int n;scanf("%d",&n); n/=2;a[0]=b[1]=1;for(int i=1;i<=n;i++) a[i]=a[i-1]*2%MOD;for(int i=2;i<=n;i++) b[i]=1ll*b[i-1]*(a[i]-3+MOD)%MOD;for(int i=2;i<=n;i++) ans=(4ll*b[i]+ans)%MOD;ans=(2ll*ans*ans%MOD+8ll*ans%MOD+10)%MOD;printf("%d\n",ans);return 0;
}