E. Bus Number

这个夜晚对瓦夏来说并不好过。他最喜欢的队伍输了，而他自己也没有取得胜利——尽管他表现完美，但队友们每次都让他失望。他必须至少再赢一次，但连败的势头却越来越长……难怪他这一夜根本没睡着。 早上，瓦夏在公交站等待去大学的公交车。瓦夏的思绪昏昏沉沉，没能清楚地记住公交车的正确编号，于是登上了编号为 $n$ 的公交车。 在公交车上，瓦夏心想，自己可能把公交车编号的数字顺序记错了。此外，他可能“看到”某些数字多次出现，但所有他看到的数字都肯定存在于真实的公交车编号中。例如，如果瓦夏看到的数字是 _2028_，那么真实的公交车编号可能是 _2028_、_8022_、_2820_ 或者仅仅是 _820_。然而，数字 _80_、_22208_、_52_ 绝对不可能是公交车编号。此外，真实的公交车编号不能以数字 _0_ 开头，这意味着像 _082_ 这样的数字也不可能是真实的公交车编号。 给定 $n$，请确定可能的公交车编号的总数。 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 瓦夏看到的公交车编号。保证该数字不以 $0$ 开头。 请输出一个整数——真实公交车编号的可能变体数量。 在第一个样例中，只有变体 $97$ 和 $79$ 是可能的。 在第二个样例中，变体（按升序排列）如下：$208$、$280$、$802$、$820$、$2028$、$2082$、$2208$、$2280$、$2802$、$2820$、$8022$、$8202$、$8220$。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 瓦夏看到的公交车编号。保证该数字不以 $0$ 开头。 ## Output 请输出一个整数——真实公交车编号的可能变体数量。 [samples] ## Note 在第一个样例中，只有变体 $97$ 和 $79$ 是可能的。在第二个样例中，变体（按升序排列）如下：$208$、$280$、$802$、$820$、$2028$、$2082$、$2208$、$2280$、$2802$、$2820$、$8022$、$8202$、$8220$。

Let $ n $ be a positive integer with decimal representation $ d_1 d_2 \dots d_k $, where $ d_1 \ne 0 $, and $ k = \lfloor \log_{10} n \rfloor + 1 $. Let $ S $ be the multiset of digits of $ n $, i.e., $ S = \{d_1, d_2, \dots, d_k\} $, with multiplicities. Let $ m_d $ denote the multiplicity of digit $ d \in \{0,1,\dots,9\} $ in $ S $. We are to count the number of distinct positive integers (without leading zeros) that can be formed by selecting a non-empty subset of the digits in $ S $ (with multiplicity not exceeded) and permuting them. That is, for each non-empty subset $ T \subseteq S $ (respecting multiplicities), let $ \ell = |T| $. The number of distinct permutations of $ T $ that do not start with 0 is: $$ \sum_{\ell=1}^{k} \sum_{\substack{T \subseteq S \\ |T| = \ell}} \left( \frac{\ell!}{\prod_{d=0}^9 m_d(T)!} - \frac{(\ell-1)!}{\prod_{d=0}^9 m_d'(T)!} \cdot [m_0(T) > 0] \right) $$ where: - $ m_d(T) $ is the multiplicity of digit $ d $ in subset $ T $, - $ m_d'(T) $ is the multiplicity of digit $ d $ in $ T \setminus \{ \text{first digit} \} $, assuming first digit is 0, - the second term subtracts permutations where the first digit is 0 (invalid numbers). But a more efficient and standard way is: Let $ \mathcal{T} $ be the set of all non-empty multisubsets of $ S $ (i.e., all possible digit multisets obtainable by choosing some digits from $ S $, respecting multiplicities). For each such multiset $ T \in \mathcal{T} $, let $ \ell = \sum_{d=0}^9 m_d(T) $, and define: - Total permutations of $ T $: $ P(T) = \frac{\ell!}{\prod_{d=0}^9 m_d(T)!} $ - Permutations with leading zero: if $ m_0(T) > 0 $, then fix 0 at front, permute remaining $ \ell-1 $ digits: $ Z(T) = \frac{(\ell-1)!}{m_0(T)-1)! \prod_{d=1}^9 m_d(T)!} $, else $ Z(T) = 0 $ Then the number of valid numbers from $ T $ is $ P(T) - Z(T) $. Thus, the total number of valid bus numbers is: $$ \sum_{\substack{T \subseteq S \\ T \ne \emptyset}} \left( \frac{|T|!}{\prod_{d=0}^9 m_d(T)!} - \begin{cases} \frac{(|T|-1)!}{(m_0(T)-1)! \prod_{d=1}^9 m_d(T)!} & \text{if } m_0(T) > 0 \\ 0 & \text{otherwise} \end{cases} \right) $$ Equivalently, we can iterate over all possible digit frequency vectors $ (f_0, f_1, \dots, f_9) $ such that $ 0 \le f_d \le m_d $ for all $ d $, and $ \sum_{d=0}^9 f_d \ge 1 $, and for each such vector: - If $ f_0 = \sum_{d=0}^9 f_d $, skip (only zeros — invalid, but $ \sum f_d \ge 1 $ and all zeros implies leading zero, so excluded anyway). - Compute total permutations: $ \frac{L!}{\prod_{d=0}^9 f_d!} $ where $ L = \sum_{d=0}^9 f_d $ - Subtract invalid ones (leading zero): if $ f_0 > 0 $, subtract $ \frac{(L-1)!}{(f_0 - 1)! \prod_{d=1}^9 f_d!} $ Thus, the final formal expression is: $$ \boxed{ \sum_{\substack{f_0=0 \\ f_1=0 \\ \vdots \\ f_9=0}}^{\substack{m_0 \\ m_1 \\ \vdots \\ m_9}} \left[ \mathbf{1}_{\sum f_d \ge 1} \cdot \left( \frac{(\sum_{d=0}^9 f_d)!}{\prod_{d=0}^9 f_d!} - \mathbf{1}_{f_0 > 0} \cdot \frac{(\sum_{d=0}^9 f_d - 1)!}{(f_0 - 1)! \prod_{d=1}^9 f_d!} \right) \right] } $$ where $ m_d $ is the multiplicity of digit $ d $ in the original number $ n $.