Teleporting Frog: Minimum Jumps to a Portal

Frog Little C has heard that NOIP is celebrating its anniversary with a competition. Excited, he journeys to Z City. Initially he is at coordinate \(x_0\). Being a frog adept at jumping, if he is currently at coordinate \(x\) then each jump moves him either to \(4x+3\) or \(8x+7\). Due to his limited stamina, he can make at most 100000 jumps.

According to Z City legend, any coordinate that is an integer multiple of \(10^9+7\) (for example, \(10^9+7,\;2\times(10^9+7),\;\ldots\)) is a teleportation portal to YZOJ.

Little C wants to know the minimum number of jumps needed in order to reach a teleportation portal. If it is impossible within 100000 jumps, output -1.

Hint: By adding 1 to both sides of the jump equations, you may notice that for each jump the transformation becomes

[ (x+1)\to \begin{cases} 4(x+1) & \text{if using } 4x+3,\ 8(x+1) & \text{if using } 8x+7. \end{cases} ]

Thus, if we define \(y=x+1\), then after a sequence of jumps the frog’s coordinate is transformed by a product of 4's and 8's, and the teleportation condition becomes \(y\equiv1\;(\bmod\;10^9+7)\). Solve for the least number of jumps \(n\) (with \(n \le 100000\)) such that there exists a choice of jumps satisfying

[ (4^{n_4} \cdot 8^{n_8})(x_0+1)\equiv1 \pmod{10^9+7}, \quad \text{with } n_4+n_8=n. ]

If no such sequence exists within 100000 moves, output -1.

inputFormat

The input consists of a single integer \(x_0\) (\(0 \le x_0 < 10^9+7\) or any integer) representing the initial coordinate.

outputFormat

Output a single integer: the minimum number of jumps needed to reach a teleportation portal. If impossible within 100000 moves, output -1.

sample

0

0