Mixed Multiplication Numbers Count

Given a positive integer \(n\), we call it a mixed multiplication number if there exist positive integers \(a\) and \(b\) such that

[ n = a \times b, ]

and the total frequency of each digit (in base 10) in the decimal representations of \(a\) and \(b\) is exactly the same as the frequency of that digit in \(n\). In other words, if you concatenate the decimal representations of \(a\) and \(b\), then after sorting the digits, it is identical to the sorted digits of \(n\).

For example:

• For \(n = 126\), we have \(a = 6\) and \(b = 21\). Since \( sorted(126) = 1,2,6 \quad \text{and} \quad sorted(6\,\|\,21) = sorted(6) \cup sorted(21) = 1,2,6, \) 126 is a mixed multiplication number.
• For \(n = 180225\), we have \(a = 225\) and \(b = 801\). One may verify that the digits match as well.

Your task is to count how many mixed multiplication numbers exist in the range \(1 \le n \le 1{,}000{,}000\) (inclusive).

inputFormat

This problem does not take any input from standard input.

outputFormat

Output a single integer representing the count of mixed multiplication numbers between 1 and 1,000,000 (inclusive).

sample

No input

116