Problem Description

$100$ can be written as a mixed fraction: $100 = 3 + \frac{69258}{714}$.

It can also be written as: $100 = 82 + \frac{3546}{197}$.

Note the feature: in the mixed fraction, the digits $1$ to $9$ each appear exactly once (digit $0$ is not included).

For mixed fractions like this, $100$ has $11$ different representations.

Input Format

Read a positive integer $N(N<10^6)$ from standard input.

Output Format

Output the total number of ways to represent $N$ as a mixed fraction formed by using the digits $1$ to $9$ exactly once each, with no repetition and no omission.

Note: You do not need to output each representation; only count how many there are.

100

11

105

6

Hint

In the original problem, the time limit is 3 seconds and the memory limit is 64 MB. This is from the 4th Lanqiao Cup Provincial Contest in 2013.

Translated by ChatGPT 5