当前没有测试数据。

循环数

题目描述

Y 同学对一种被称为“循环数”的正整数非常感兴趣。

一个正整数 $X$ 被称为“循环数”，当且仅当它同时满足以下所有条件：

1. $X$ 的十进制表示中不包含数字 $0$。
2. $X$ 的十进制表示中没有任何两个相同的数字。
3. 假设 $X$ 有 $K$ 位，其十进制表示从左到右依次为 $d_1, d_2, \dots, d_K$。我们定义一个在数位下标集合 $\{1, 2, \dots, K\}$ 上的移动规则：若当前在第 $i$ 位（数字为 $d_i$），则向右移动 $d_i$ 步。若移动超出了最右端，则折返至最左端继续循环移动。即下一个位置的下标 $j$ 的计算公式为：$$j = ((i - 1 + d_i) \bmod K) + 1$$
4. 从起点第 $1$ 位开始，按照上述规则连续移动恰好 $K$ 次。在此过程中，要求经过的 $K$ 个位置互不相同（即每个数位必须恰好被访问一次），并且第 $K$ 次移动后的位置必须重新回到起点第 $1$ 位。

例如，$81362$ 是一个循环数（此时 $K=5$）：

• 第 $1$ 步：从第 $1$ 位（数字 $8$）开始，移动 $8$ 步，到达第 $4$ 位（数字 $6$）；
• 第 $2$ 步：从第 $4$ 位（数字 $6$）开始，移动 $6$ 步，到达第 $5$ 位（数字 $2$）；
• 第 $3$ 步：从第 $5$ 位（数字 $2$）开始，移动 $2$ 步，到达第 $2$ 位（数字 $1$）；
• 第 $4$ 步：从第 $2$ 位（数字 $1$）开始，移动 $1$ 步，到达第 $3$ 位（数字 $3$）；
• 第 $5$ 步：从第 $3$ 位（数字 $3$）开始，移动 $3$ 步，重新回到起点的第 $1$ 位（数字 $8$）。 该数每个位置恰好被访问一次，且最后回到了起点，同时不含 $0$ 且无重复数字。

现在，给定一个正整数 $M$，请你编写程序帮助 Y 同学找出最小的、且严格大于 $M$ 的循环数 $M'$。

输入格式

第一行包含一个正整数 $M$。

输出格式

输出一行一个正整数，表示符合条件的最小循环数 $M'$。

样例

样例输入 #1

81361

样例输出 #1

81362

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le M \le 10^9$。

数据保证必定存在满足条件的 $M'$，且 $M' \le 2^{32}-1$。因为答案可能会超出 32 位有符号整数的表示范围，请使用 64 位整数类型进行计算与输出。