#include #pragma GCC optimize("O3") using namespace std; #if __cplusplus < 201103L #error C++11 or higher expected. #endif constexpr int CPPV = (__cplusplus / 100 % 100); // C++ Version // define #define endl "\n" #ifdef LOCAL #define lout cerr #else ostream devnull(0); #define lout devnull #endif #define dump(x) lout << #x << " = " << (x) << endl; #define all(a) (a).begin(), (a).end() // rep // Inspired by: // https://github.com/kurokoji/.cpp-Template/blob/master/template/template2.cpp #define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME #define rep(...) \ GET_MACRO(__VA_ARGS__, rep4, rep3, rep2, rep1) \ (__VA_ARGS__) #define rep1(n) rep2(_, n) #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, n) rep4(i, a, n, 1) #define rep4(i, a, n, d) rep5(i, a, n, d, <) #define rep5(i, a, n, d, o) \ for (auto i = decltype(n)(a), i##_len = (n); i o i##_len; i += (d)) #define rrep(...) \ GET_MACRO(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1) \ (__VA_ARGS__) #define rrep1(a) rrep2(_, a) #define rrep2(i, a) rrep3(i, a, 0) #define rrep3(i, a, n) rrep4(i, a, n, -1) #define rrep4(i, a, n, d) rep5(i, (a)-1, n, d, >=) #define repc(...) \ GET_MACRO(__VA_ARGS__, repc4, repc3, repc2, repc1) \ (__VA_ARGS__) #define repc1(n) repc2(_, n) #define repc2(i, n) repc3(i, 0, n) #define repc3(i, a, n) repc4(i, a, n, 1) #define repc4(i, a, n, d) rep5(i, a, n, d, <=) // alias using ll = long long; using lint = long long; // func template void vcin(C &c) { for (auto &&a : c) { cin >> a; } } template void vcin(C &c, D &d) { for (auto it1 = c.begin(), it2 = d.begin(); it1 != c.end() && it2 != d.end(); it1++, it2++) { cin >> *it1 >> *it2; } } template void vcout(const C &c, const string delimiter = " ") { for (auto it = c.begin(); it != c.end(); it++) { if (it != c.begin()) cout << delimiter; cout << *it; } } template inline T input() { T x; cin >> x; return (x); } template inline void chmax(T &x, const T y) { if (x < y) x = y; } template inline void chmin(T &x, const T y) { if (x > y) x = y; } #if 1 // http://beet-aizu.hatenablog.com/entry/2018/04/08/145516 template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) { return vector(ts...))>(a, make_v(ts...)); } template typename enable_if::value == 0>::type fill_v(T &t, const V &v) { t = v; } template typename enable_if::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); } #endif constexpr int INF = 1 << 24; constexpr lint LINF = 1LL << 48; inline lint bit(int n) { return 1LL << n; } inline bool bitof(lint n, int i) { return (n >> i) & 1; } template inline bool between(T a, T x, T b) { return a <= x && x <= b; } void solve(); signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); solve(); return 0; } void solve() { constexpr int MOD = (int)1e9 + 7; string A, B; cin >> A >> B; const int n = B.size(); vector a, b; a.reserve(n); rep(n - A.size()) { a.push_back(0); } for (char c : A) { a.push_back(c - '0'); } b.reserve(n); for (char c : B) { b.push_back(c - '0'); } #ifdef LOCAL vcout(a, " "); cout << endl; vcout(b, " "); cout << endl; #endif auto dp = make_v(n + 1, 2, 2, 2, 3, 8); dp[0][0][0][0][0][0] = 1; rep(i, n) repc(j, 1) repc(k, 1) repc(l, 1) rep(m, 3) rep(o, 8) repc(d, j ? 0 : a[i], k ? 9 : b[i]) { dp[i + 1][j || d > a[i]][k || d < b[i]][l || d == 3][(m + d) % 3][(o * 10 + d) % 8] += dp[i][j][k][l][m][o]; dp[i + 1][j || d > a[i]][k || d < b[i]][l || d == 3][(m + d) % 3][(o * 10 + d) % 8] %= MOD; } lint ans = 0; repc(j, 1) repc(k, 1) repc(l, 1) rep(m, 3) rep(o, 8) { if ((l || m == 0) && o != 0) { ans += dp[n][j][k][l][m][o]; ans %= MOD; } } cout << ans << endl; }