#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) typedef long long ll; const int mod = 1e9 + 7; ll dp[100005][2][2][3][8]; // 調べた桁数、小さくなることが確定しているか、3がつくか、mod3、mod8 ll calc(string s, bool less) { int len = s.length(); FOR(i,0,len+1) FOR(j,0,2) FOR(k,0,2) FOR(l,0,3) FOR(m,0,8) { dp[i][j][k][l][m] = 0; } dp[0][0][0][0][0] = 1; FOR(i,0,len) FOR(j,0,2) FOR(k,0,2) FOR(l,0,3) FOR(m,0,8) { int lim = j ? 9 : s[i] - '0'; FOR(d,0,lim+1) { (dp[i+1][j||d> A >> B; ll b = calc(B,0); ll a = calc(A,1); cout << (b - a + mod) % mod << endl; return 0; }