package main import ( "bufio" "fmt" "io" "os" "strconv" ) var iost *Iost type Iost struct { Scanner *bufio.Scanner Writer *bufio.Writer } func NewIost(fp io.Reader, wfp io.Writer) *Iost { const BufSize = 2000005 scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, BufSize), BufSize) return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)} } func (i *Iost) Text() string { if !i.Scanner.Scan() { panic("scan failed") } return i.Scanner.Text() } func (i *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x } func (i *Iost) GetNextInt() int { return i.Atoi(i.Text()) } func (i *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func (i *Iost) GetNextInt64() int64 { return i.Atoi64(i.Text()) } func (i *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func (i *Iost) GetNextFloat64() float64 { return i.Atof64(i.Text()) } func (i *Iost) Print(x ...interface{}) { fmt.Fprint(i.Writer, x...) } func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) } func (i *Iost) Println(x ...interface{}) { fmt.Fprintln(i.Writer, x...) } func isLocal() bool { return os.Getenv("NICKEL") == "BACK" } func main() { fp := os.Stdin wfp := os.Stdout if isLocal() { fp, _ = os.Open(os.Getenv("WELL_EVERYBODY_LIES_TOO_MUCH")) } iost = NewIost(fp, wfp) defer func() { iost.Writer.Flush() }() solve() } func solve() { SetMod(Mod1000000007) a := iost.Text() b := iost.Text() p := iost.GetNextInt() iost.Println(g(b, 0).Sub(g(a, 1)).Sub(f(b, 0, p)).Add(f(a, 1, p))) } func f(s string, sub, p int) Mint { n := len(s) ss := make([]int, n) for i := 0; i < n; i++ { ss[i] = int(s[i] - '0') } ss[n-1] -= sub for i := n - 2; i >= 0; i-- { if ss[i+1] < 0 { ss[i+1] += 10 ss[i]-- } } if ss[0] == 0 { ss = ss[1:] } for p%10 == 0 && len(ss) > 0 { p /= 10 ss = ss[:len(ss)-1] } n = len(ss) if n == 0 { return 0 } dp := make([][2][2][24]Mint, n+1) dp[n][0][0][0] = 1 var ans Mint m := 1 tom := make([]int, 24) isMod3 := make([]bool, 24) isMod8 := make([]bool, 24) for i := 0; i < 24; i++ { tom[i] = i * 10 % 24 isMod3[i] = i%3 == 0 isMod8[i] = i%8 == 0 } for i := n - 1; i >= 0; i-- { for j := 0; j < 2; j++ { for k := 0; k < 2; k++ { for l := 0; l < 24; l++ { for d := 0; d < 10; d++ { tj := 0 if ss[i]-j < d { tj = 1 } tk := k if d == 3 { tk = 1 } tl := (l + d*m) % 24 dp[i][tj][tk][tl].AddAs(dp[i+1][j][k][l]) if d == 0 { continue } if tk == 0 && !isMod3[tl] { continue } if !isMod8[tl] { continue } if i > 0 || tj == 0 { ans += dp[i+1][j][k][l] } } } } } ans %= Mod1000000007 m = tom[m] } return ans } func g(s string, sub int) Mint { n := len(s) ss := make([]int, n) for i := 0; i < n; i++ { ss[i] = int(s[i] - '0') } ss[n-1] -= sub for i := n - 2; i >= 0; i-- { if ss[i+1] < 0 { ss[i+1] += 10 ss[i]-- } } if ss[0] == 0 { ss = ss[1:] } n = len(ss) if n == 0 { return 0 } dp := make([][2][2][3]Mint, n+1) dp[n][0][0][0] = 1 var ans Mint m := 1 tom := make([]int, 3) isMod3 := make([]bool, 3) for i := 0; i < 3; i++ { tom[i] = i * 10 % 3 isMod3[i] = i%3 == 0 } for i := n - 1; i >= 0; i-- { for j := 0; j < 2; j++ { for k := 0; k < 2; k++ { for l := 0; l < 3; l++ { for d := 0; d < 10; d++ { tj := 0 if ss[i]-j < d { tj = 1 } tk := k if d == 3 { tk = 1 } tl := (l + d*m) % 3 dp[i][tj][tk][tl].AddAs(dp[i+1][j][k][l]) if d == 0 { continue } if tk == 0 && !isMod3[tl] { continue } if i > 0 || tj == 0 { ans += dp[i+1][j][k][l] } } } } } ans %= Mod1000000007 m = tom[m] } return ans } // Mod constants. const ( Mod1000000007 = 1000000007 Mod998244353 = 998244353 ) var ( mod Mint fmod func(Mint) Mint ) // Mint treats the modular arithmetic type Mint int64 // SetMod sets the mod. It must be called first. func SetMod(newmod Mint) { switch newmod { case Mod1000000007: fmod = staticMod1000000007 case Mod998244353: fmod = staticMod998244353 default: mod = newmod fmod = dynamicMod } } func dynamicMod(m Mint) Mint { m %= mod if m < 0 { return m + mod } return m } func staticMod1000000007(m Mint) Mint { m %= Mod1000000007 if m < 0 { return m + Mod1000000007 } return m } func staticMod998244353(m Mint) Mint { m %= Mod998244353 if m < 0 { return m + Mod998244353 } return m } // Mod returns m % mod. func (m Mint) Mod() Mint { return fmod(m) } // Inv returns modular multiplicative inverse func (m Mint) Inv() Mint { return m.Pow(Mint(0).Sub(2)) } // Pow returns m^n func (m Mint) Pow(n Mint) Mint { p := Mint(1) for n > 0 { if n&1 == 1 { p.MulAs(m) } m.MulAs(m) n >>= 1 } return p } // Add returns m+x func (m Mint) Add(x Mint) Mint { return (m + x).Mod() } // Sub returns m-x func (m Mint) Sub(x Mint) Mint { return (m - x).Mod() } // Mul returns m*x func (m Mint) Mul(x Mint) Mint { return (m * x).Mod() } // Div returns m/x func (m Mint) Div(x Mint) Mint { return m.Mul(x.Inv()) } // AddAs assigns *m + x to *m and returns m func (m *Mint) AddAs(x Mint) *Mint { *m = m.Add(x) return m } // SubAs assigns *m - x to *m and returns m func (m *Mint) SubAs(x Mint) *Mint { *m = m.Sub(x) return m } // MulAs assigns *m * x to *m and returns m func (m *Mint) MulAs(x Mint) *Mint { *m = m.Mul(x) return m } // DivAs assigns *m / x to *m and returns m func (m *Mint) DivAs(x Mint) *Mint { *m = m.Div(x) return m }