我们设\(f_i\)为\(i\)阶台阶时的答案，距题意易得\(f_i=f_{i-1}+2f_{i-2}+2f_{i-3}+f_{i-4}\).

矩阵快速幂即可

代码如下

#include <iostream>
using namespace std;
const long long int mod = 1000000009;
struct Matrix
{
    int n, m;
    long long int a[ 110 ][ 110 ] = {};
    Matrix( int n, int m )
    {
        this->n = n;
        this->m = m;
    };
    void print( void )
    {
        for ( int i = 0; i < n; i++ )
        {
            for ( int j = 0; j < m; j++ )
            {
                cerr << a[ i ][ j ] << " ";
            }
            cerr << endl;
        }
    }
    Matrix operator*( Matrix b )
    {
        Matrix ans = Matrix( 4, 4 );
        for ( int i = 0; i < 4; i++ )
        {
            for ( int k = 0; k < 4; k++ )
            {
                for ( int j = 0; j < 4; j++ )
                {
                    ans.a[ i ][ j ] += ( a[ i ][ k ] * b.a[ k ][ j ] ) % mod;
                    ans.a[ i ][ j ] %= mod;
                }
            }
        }
        return ans;
    }
};
Matrix base = Matrix( 4, 4 ), ans = Matrix( 4, 4 );
void make( void )
{
    base.a[ 0 ][ 0 ] = base.a[ 0 ][ 3 ]  = 1;
    base.a[0][1]=base.a[0][2]=2;
    base.a[1][0]=base.a[2][1]=base.a[3][2]=1;
    ans.a[ 0 ][ 0 ] = 1;
    ans.a[ 0 ][ 1 ] = 3;
    ans.a[ 0 ][ 2 ] = 7;
    ans.a[ 0 ][ 3 ] = 16;
    ans.a[ 0 ][ 4 ] = 37;
}
void pow( long long int k )
{
    while ( k )
    {
        if ( k & 1 )
        {
            ans = base * ans;
        }
        base = base * base;
        k >>= 1;
    }
}
int main ()
{
    long long int n;
    cin>>n;
    make();
    pow(n);
    cout<<ans.a[0][0]%mod<<endl;
}