思路就是数位 dp,除一个特判外，全 RE 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
int dp[25][11],k,digit[25];
int work1(int x){
	int cnt=0,ans=0;
	for(cnt=1;cnt<=x;cnt++){
		digit[cnt]=0;
	}
	digit[++cnt]=1;
	for(int i=1;i<cnt;i++){
		for(int j=1;j<10;j++){
			ans+=dp[i][j];
			ans%=mod;
		}
	}
	for(int i=1;i<digit[cnt];i++){
		ans=ans+dp[cnt][i];
		ans%=mod;
	}
	for(int i=cnt-1;i>=1;i--){
		for(int j=0;j<digit[i];j++){
			if(abs(digit[i+1]-j)<=2){
				ans+=dp[i][j];
				ans%=mod;
			}
		}
		if(abs(digit[i]-digit[i+1])>2)break;
	}
	return ans;
}
int work2(int x){
	int cnt=0,ans=0;
	for(cnt=1;cnt<x;cnt++){
		digit[cnt]=0;
	}
	digit[++cnt]=1;
	for(int i=1;i<cnt;i++){
		for(int j=1;j<10;j++){
			ans+=dp[i][j];
			ans%=mod;
		}
	}
	for(int i=1;i<digit[cnt];i++){
		ans=ans+dp[cnt][i];
		ans%=mod;
	}
	for(int i=cnt-1;i>=1;i--){
		for(int j=0;j<digit[i];j++){
			if(abs(j-digit[i+1])<=2){
				ans+=dp[i][j];
				ans%=mod;
			}
		}
		if(abs(digit[i]-digit[i+1])>2)break;
	}
	return ans;
}
signed main(){ 
	for(int i=0;i<10;i++){
		dp[1][i]=1;
	}
	for(int i=2;i<=20;i++){
		for(int j=0;j<10;j++){
			for(int k=0;k<10;k++){
				if(abs(j-k)<=2){
					dp[i][j]+=dp[i-1][k];
					dp[i][j]%=mod;
				}
			}
		}
	}
	cin>>k;
	if(k==1){
		cout<<10;
		exit(0);
	}
	k--;
	cout<<(work1(k)-work2(k)+mod)%mod;
	return 0;
}