#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] = {2, 3, 3}; dp[0][1] = {1, 0, 0}; for(int i : range(p)) { for(int k : range(3)) { for(int d : range(10)) { dp[i+1][d==3][(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 k : range(3)) { res += dp[i][1][k]; } res += dp[i][0][0]; } printf("%lld\n", res); return 0; }