问题描述

一个正整数 x 被称为“321-like 数”，当且仅当它满足以下条件：

• x 的各位数字从上到下严格递减。
• 换句话说，如果 x 有 d 位数字，对于每一个整数 i，使得 1 ≤ i < d，成立：
  • 第 i 位的数字 > 第 (i+1) 位的数字。

需要注意的是，所有一位数的正整数都是 321-like 数。

例如，321、96410 和 1 是 321-like 数，而 123、2109 和 86411 不是。

要求找到第 K 小的 321-like 数。

输入格式

输入包含一个整数 K，表示要求的 321-like 数的排名。

输出格式

输出第 K 小的 321-like 数作为一个整数。

输入约束

• 所有输入值为整数。
• 1 ≤ K，至少存在 K 个 321-like 数。

示例输入 1

15

示例输出 1

32

​解释​： 从小到大排列的 321-like 数有： 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, … 第 15 个最小的 321-like 数是 32。

示例输入 2

321

示例输出 2

9610

示例输入 3

777

示例输出 3

983210