金坷垃
题目背景
@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$取模(富土康从不用1e9+7和998244353)
输入输出格式
输入格式
一个数$k$
输出格式
合格的第$k$个金坷垃的初始深度对$123456789$取模后的结果
输入输出样例
输入样例 #1
1
输出样例 #1
1
输入样例 #2
2
输出样例 #2
2
说明
(简单死了。。。)
(给不会的人一点福利:数据里有一个是1)
对于30%的数据,$k$<=$10^5$;
对于70%的数据,$k$<=$10^9$;
对于100%的数据,$k$<=$10^{18}$;