Counting Smaller Numbers by Reordering

Given a number \(N\) (without leading zeros), you are allowed to remove any number of the digit \(0\) (possibly none) from \(N\) and then reorder the remaining digits arbitrarily. The resulting number must not have leading zeros. Count how many distinct numbers smaller than \(N\) can be obtained by this process.

Let \(N\) have a total of \(L\) digits with exactly \(k\) zeros, and let \(M\) be the multiset of nonzero digits (which must always be kept). For any \(m\) such that \(0 \le m \le k\), consider the multiset

[ S = M \cup {\underbrace{0,0,\dots,0}_{m}}]

which has (|M|+m) digits. A permutation of (S) is valid if it does not begin with (0). For the case (m < k) the resulting number has fewer than (L) digits and is automatically less than (N). For (m=k) the number has (L) digits and must be counted only if it is strictly less than (N).

The answer is the sum over all valid distinct permutations from all possible choices of \(m\) (with \(0 \le m \le k\)), subtracting \(1\) to remove \(N\) itself (which is one of the permutations when \(m=k\)).

inputFormat

The input is a single line containing the number \(N\) (as a string of digits, without leading zeros).

outputFormat

Output a single integer representing the number of distinct valid numbers (obtained by deleting some or none of the zeros and reordering the remaining digits) that are strictly less than \(N\).

sample

105

2