F. 810975
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\text{Gunshin}$$$ 最近很喜欢一串神秘数字 "810975"，所以他喜欢所有没有前导零的且含有"810975"作为子序列的数字。 一个数字 $$$x$$$ 含有子序列 $$$s$$$ 表示从 $$$x$$$中 删除若干数字后能得到 $$$s$$$。 $$$\text{Gunshin}$$$ 想知道第$$$k$$$大的他喜欢的数字是多少,请你回答他。

Input

输入一个正整数$$$k(1\leq{k}\leq{10^{15}})$$$。

Output

输出一个数，表示第$$$k$$$大$$$\text{Gunshin}$$$喜欢的数。

Examples
Input
1
Output
810975
Input
2
Output
1810975
Input
12
Output
8102975
Input
1000000000000000
Output
220387241614091751