#include #define int long long using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define INF (1ll<<60) typedef pair pii; #define FI first #define SE second #define all(s) s.begin(),s.end() #define RREP(i,n) for(int i=(n)-1;i>=0;--i) string A; string B; const int mod = 1000000007; int dp[10001][2][2][3][8]; //桁,未満確定(0未定1確定),3つく(0つかない1つく),mod3,mod8 signed main() { cin >> A >> B; dp[0][0][0][0][0] = 1; rep(i,B.length()) { rep(j,2) { rep(k,2) { rep(l,3) { rep(m,8) { int lim = j ? 9ll : B[i] - '0'; rep(d,lim+1) { (dp[i + 1][j || d < lim][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] += dp[i][j][k][l][m]) %= mod; } } } } } } int ansB = 0; rep(j,2) { rep(l,3) { rep(m,7) { ansB += dp[B.length()][j][1][l][m + 1] % mod; } } } rep(j,2) { rep(m,7) { ansB += dp[B.length()][j][0][0][m + 1] % mod; } } string AA = A; memset(dp, 0, sizeof(dp)); dp[0][0][0][0][0] = 1; rep(i,AA.length()) { rep(j,2) { rep(k,2) { rep(l,3) { rep(m,8) { int lim = j ? 9ll : AA[i] - '0'; rep(d,lim+1) { (dp[i + 1][j || d < lim][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] += dp[i][j][k][l][m]) %= mod; } } } } } } int ansA = 0; rep(j,2) { rep(l,3) { rep(m,7) { ansA += dp[AA.length()][j][1][l][m + 1] % mod; } } } rep(j,2) { rep(m,7) { ansA += dp[AA.length()][j][0][0][m + 1] % mod; } } int ans = ((ansB + mod) - ansA) % mod; int mod3 = 0, mod8 = 0; bool a = false; rep(i,A.length()) { if (A[i] == '3') { a = true; } mod3 += A[i] - '0'; mod3 %= 3; mod8 *= 10; mod8 += A[i] - '-'; mod8 %= 8; } if (a || mod3 == 0) { if (mod8 != 0) { cout << (ans + 1) % mod << endl; return 0; } } cout << ans << endl; }