金坷垃

@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

2

2

（简单死了。。。） （给不会的人一点福利：数据里有一个是1） 对于30%的数据，$k$<=$10^5$; 对于70%的数据，$k$<=$10^9$; 对于100%的数据，$k$<=$10^{18}$；