题目背景

@rainheavy 原创。

这是一道巨（du）水（liu）题。

第一届中国国际博览会于 2018 年 11.5 ~ 11.10 在上海举行，特朗普统治的国家——美丽国带来了金坷垃。这是一种神奇的产品，据他们的广告所说：肥料用了金坷垃，能吸收 20 米以下的氮磷钾。

可是，在经过富土（tu）康的质检员 DevZhu 质检的时候发现出了点问题，金坷垃的效果并不像广告所说的那样。毕竟植物的根只能到深度为 $1$ 的位置，金坷垃的效果有限。

题目描述

它只有如下的效果：（以 $20$ 为例）

$20$ 的真因子有 $10,5,4,2,1$。

从地下 $20$ 米深处可以往上跳一个约数的长度。（比如 $10$）

现在它在 $10$ 米处，$10$ 的真因子有 $5,2,1$。

再跳一个 $5$，为 $5$，$5$ 的真因子有 $1$。

再跳 $1$ 个 $1$，为 $4$，$4$ 的真因子有 $2,1$。

$1$ 已用过，不能再用。

再跳一个 $2$，为 $2$。$2$ 的真因子有 $1$。

$1$ 已用过，此时没法再跳了。此时的深度为 $2$。

按上述要求跳，把所有符合要求的能跳的所有情况全试一遍，只要有一种情况最后结果为 $1$，这个肥料就合格，否则不合格。

DevZhu 面对一大堆待检验的金坷垃，并不想检验那么多，他想问问你有哪些金坷垃是合格的，在这些合格的金坷垃中，初始深度排在第 $k$ 个的是哪一个。

把合格的金坷垃按初始深度从小到大排，请输出第 $k$ 个金坷垃的初始深度，对 $123456789$ 取模。（富土康从不用 $10^9+7$ 和 $998244353$）

输入格式

一个数 $k$。

输出格式

合格的第 $k$ 个金坷垃的初始深度对 $123456789$ 取模后的结果。

1

1

2

2

提示

（简单死了。。。）

（给不会的人一点福利：有一个数据 $k=1$。）

对于 $30\%$ 的数据，$k \le 10^5$；

对于 $70\%$ 的数据，$k \le 10^9$；

对于 $100\%$ 的数据，$k \le 10^{18}$。