#include #include using namespace std; using i64 = long long; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x>> dp(p+1, vector>(2, vector(3))); dp[0][0][0] = 2; dp[0][0][1] = 3; dp[0][0][2] = 3; dp[0][1][0] = 1; dp[0][1][1] = 0; dp[0][1][2] = 0; for(int i : range(p)) { for(int k : range(3)) { for(int d : range(10)) { if(d == 3) { dp[i+1][1][(k+d)%3] += dp[i][0][k]; } else { dp[i+1][0][(k+d)%3] += dp[i][0][k]; } dp[i+1][1][(k+d)%3] += dp[i][1][k]; } } } i64 res = 0; for(int i : range(p+1)) { for(int d : range(3)) { res += dp[i][1][d]; } res += dp[i][0][0]; } printf("%lld\n", res); return 0; }