题目描述

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

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

输入格式

单个整数：表示 $n$。

输出格式

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

数据范围

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

样例数据

输入:

1

输出:

1

输入:

11

输出:

12

说明:

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

输入:

8877690

输出:

9876543210