说明

众所周知，yqdjl6非常喜欢数学，现在yqdjl6遇到了一个大麻烦，对于0~9十个数，yqdjl6想知道在所有0~9的全排列中，第N个排列的是多少。这道题对于yqdjl6来说太难了，聪明的你能帮帮他吗？其中，第i个排列的定义为在所有0~9的全排列中，有i-1个排列的字典序比当前这个排列的字典序小。

输入格式

输入包括一行，包含一个整数$N$ $(1 \leq N \leq 3628800)$

输出格式

输出包括一行，一组10个数字的排列

样例

1

0123456789

样例

2

0123456798

提示

对于0、1、2三个数字的全排列有六种，按照字母序排列如下：012、021、102、120、201、210