100 可以表示为带分数的形式：100=3+69258714

还可以表示为：100=82+3546197

注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<106

输入样例1：

1
100

输出样例1：

1
11

输入样例2：

1
105

输出样例2：

1
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c) {
    long long b = n * (long long)c - a * c; // c可能有8位数，那么和n乘起来以后就会溢出int，那么b就可能变成负数，从而它的个位数字的余数也可能是负数，那么backup[x]的下标就可能是负数，所以下标就越界了。

    if (!a || !b || !c) return false; // 判零

    memcpy(backup, st, sizeof st); // 用于判重的备份
    while (b) {
        int x = b % 10;
        b /= 10;
        if (!x || backup[x]) return false; // 两种情况返回false: 1. x是零 2. x已经出现过
        backup[x] = true;
    }

    // 判断是否有数没用过
    for (int i = 1; i <= 9; i++)
        if (!backup[i])
            return false;
    
    return true;
}

void dfs_c(int u, int a, int c) {
    if (u == n) return; // n用完了，剪枝

    if (check(a, c)) ans++;

    for (int i = 1; i <= 9; i++)
        if (!st[i]) {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
}

void dfs_a(int u, int a) {
    if (a >= n) return;
    if (a) dfs_c(u, a, 0);

    for (int i = 1; i <= 9; i++)
        if (!st[i]) {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
}

int main() {
    cin >> n;
    dfs_a(0, 0);
    cout << ans << '\n';
    return 0;
}