#include using namespace std; #define FOR(i,s,e) for(int (i)=(s);(i)<(int)(e);(i)++) #define REP(i,e) FOR(i,0,e) #define RFOR(i,e,s) for(int (i)=(e)-1;(i)>=(int)(s);(i)--) #define RREP(i,e) RFOR(i,0,e) #define all(o) (o).begin(), (o).end() #define psb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) typedef long long ll; typedef pair PII; typedef priority_queue PQI; typedef priority_queue PQII; const double EPS = 1e-10; const int P = 20; int p; ll dp[P+1][2][3][2]; //poss, less, mod 3, has 3 ll calc(string x) { int n = (int)x.size(); memset(dp, 0, sizeof(dp)); dp[0][0][0][0] = 1; REP(i,n) REP(j,2) REP(k,3) REP(l,2) { int lim = j ? 9 : x[i]-'0'; REP(d,lim+1) dp[i+1][j || d