这题。。。一上来就是水倍增，AC了。。。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,a[15][15],b[15][15],ans;
void f(int n){
    if(n==1){
        for(int i=0;i<=9;i++) b[i][i]=1;
        return;
    }
    if(n&1LL){
        f(n>>1LL);
        swap(a,b);
        for(int i=0;i<=9;i++){
            for(int j=0;j<=9;j++){
            	b[i][j]=0;
                for(int k=0;k<=9;k++){
                    for(int h=max(k-2,0LL);h<=min(k+2,9LL);h++){
                        for(int p=max(j-2,0LL);p<=min(j+2,9LL);p++){
                        	b[i][j]=(b[i][j]+a[i][k]*a[h][p])%mod;
						}
                    }
                }
            }
        }
    }else{
        f(n>>1LL);
        swap(a,b);
        for(int i=0;i<=9;i++){
            for(int j=0;j<=9;j++){
            	b[i][j]=0;
                for(int k=0;k<=9;k++){
                    for(int h=max(k-2,0LL);h<=min(k+2,9LL);h++) b[i][j]=(b[i][j]+a[i][k]*a[h][j])%mod;
                }
            }
        }
    }
}
signed main(){
    scanf("%lld",&n);
    if(n==1){
    	printf("10");
    	return 0;
	}
    f(n);
    for(int i=1;i<=9;i++){
        for(int j=0;j<=9;j++) ans=(ans+b[i][j])%mod;
    }
    printf("%lld",ans);
    return 0;
}