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) s := iost.Text() n := len(s) ss := make([]int, n) for i := 0; i < n; i++ { ss[i] = int(s[i] - '0') } dp := make([][2]Mint, n+1) dp[n][0] = 1 var ans Mint for i := n - 1; i >= 0; i-- { for j := 0; j < 2; j++ { for k := 1; k < 10; k++ { tj := 0 if ss[i]-j < k { tj = 1 } dp[i][tj].AddAs(dp[i+1][j].Mul(Mint(k))) if i > 0 || tj == 0 { ans.AddAs(dp[i+1][j].Mul(Mint(k))) } } } } iost.Println(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 }