```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const (
	States = 9
	Masks  = 1 << 9
	MaxK   = 18
	INF    int64 = 1 << 62
)

type Matrix struct {
	a [States * States]int64
}

func identity() Matrix {
	var m Matrix
	for i := 0; i < States*States; i++ {
		m.a[i] = INF
	}
	for i := 0; i < States; i++ {
		m.a[i*States+i] = 0
	}
	return m
}

func multiply(x, y Matrix) Matrix {
	var z Matrix
	for i := 0; i < States*States; i++ {
		z.a[i] = INF
	}
	for i := 0; i < States; i++ {
		ib := i * States
		for k := 0; k < States; k++ {
			xv := x.a[ib+k]
			if xv >= INF {
				continue
			}
			kb := k * States
			for j := 0; j < States; j++ {
				yv := y.a[kb+j]
				if yv >= INF {
					continue
				}
				v := xv + yv
				idx := ib + j
				if v < z.a[idx] {
					z.a[idx] = v
				}
			}
		}
	}
	return z
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var s string
	fmt.Fscan(in, &s)

	ident := identity()

	var base [Masks]Matrix
	base[0] = ident
	for mask := 1; mask < Masks; mask++ {
		var m Matrix
		for i := 0; i < States*States; i++ {
			m.a[i] = INF
		}
		for d := 1; d <= 9; d++ {
			if mask&(1<<(d-1)) != 0 {
				m.a[d-1] = 1
			}
		}
		for i := 1; i < States; i++ {
			m.a[i*States+(i-1)] = 0
		}
		base[mask] = m
	}

	var nextMask [Masks][10]int
	for mask := 0; mask < Masks; mask++ {
		nextMask[mask][0] = mask
		for d := 1; d <= 9; d++ {
			nextMask[mask][d] = mask | (1 << (d - 1))
		}
	}

	var dp [MaxK + 1][Masks]Matrix
	for mask := 0; mask < Masks; mask++ {
		dp[0][mask] = base[mask]
	}
	for k := 1; k <= MaxK; k++ {
		for mask := 0; mask < Masks; mask++ {
			res := ident
			for d := 0; d <= 9; d++ {
				res = multiply(dp[k-1][nextMask[mask][d]], res)
			}
			dp[k][mask] = res
		}
	}

	res := ident
	mask := 0
	n := len(s)
	for i := 0; i < n; i++ {
		cur := int(s[i] - '0')
		rem := n - i - 1
		for d := 0; d < cur; d++ {
			res = multiply(dp[rem][nextMask[mask][d]], res)
		}
		mask = nextMask[mask][cur]
	}
	res = multiply(base[mask], res)

	out := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(out, res.a[0])
	out.Flush()
}
```