题目描述

如果一个正整数的十进制表示的每位数码都不同，则称它为独特数。

将所有独特数从小到大排列，给定 $n$，请求出第 $n$ 小的独特数（$0$ 不算独特数）。

输入格式

单个整数：表示 $n$。

输出格式

单个整数：表示第 $n$ 个独特数。

1

1

11

12

样例解释 2

1到12之间只有11不是独特数

8877690

9876543210

数据范围

• 对于 $50\%$ 的数据，$1\leq n\leq 1000$
• 对于 $100\%$ 的数据，$1\leq n\leq 4,000,000$
• 对于附加数据，$1\leq n\leq 8,877,690$