//#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i) #define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i) #define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++) #define SORT(v, n) sort(v, v+n) #define REVERSE(v) reverse((v).begin(), (v).end()) using namespace std; using ll = long long; const ll MOD=1000000007LL; typedef pair P; ll ADD(ll x, ll y) { return (x+y) % MOD; } ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; } ll MUL(ll x, ll y) { return x*y % MOD; } ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; } ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); } ll nl, nm; //i桁目, smaller, 3がつく, mod 3, mod 8 ll dp[100001][2][2][3][8]; ll calc(string s){ memset(dp, 0, sizeof(dp)); ll n = s.size(); dp[0][0][0][0][0] = 1; REP(i, n) { ll x = s[i]-'0'; REP(j, 2){ REP(k, 2){ REP(l, 3){ REP(m, 8){ ll lim = (j ? 9 : x); REP(d, lim+1) (dp[i+1][j||(d> a >> b; //cout << (MOD + calc(b) - calc(a)) % MOD << endl; s = b; memset(dp, 0, sizeof(dp)); ll n = s.size(); dp[0][0][0][0][0] = 1; REP(i, n) { ll x = s[i]-'0'; REP(j, 2){ REP(k, 2){ REP(l, 3){ REP(m, 8){ ll lim = (j ? 9 : x); REP(d, lim+1) (dp[i+1][j||(d