409284: GYM103476 E Redundant Binary Representations

You probably know that every number has a unique representation in the binary number system. For example, $$$21 = 16 + 4 + 1 = 10101_2$$$.

Let's introduce the concept of the redundant binary number system. In this system, the weights of digits are powers of two, but every digit can be equal to $$$0$$$, $$$1$$$, or $$$2$$$, without leading zeros. This representation has many advantages, but numbers can have multiple representations; for example, there are $$$5$$$ ways to represent $$$21$$$ in the redundant binary number system:

• $$$21 = 16 + 4 + 1 = 10101_2$$$
• $$$21 = 16 + 2 + 2 + 1 = 10021_2$$$
• $$$21 = 8 + 8 + 4 + 1 = 2101_2$$$
• $$$21 = 8 + 8 + 2 + 2 + 1 = \textbf{2021}_2$$$
• $$$21 = 8 + 4 + 4 + 2 + 2 + 1 = 1221_2$$$

Denote the number of ways to represent $$$n \ge 0$$$ as $$$a(n)$$$. We consider $$$0$$$ to have one representation, so that $$$a(0) = 1$$$.

What problem involving $$$a(n)$$$ can we come up with? Calculate $$$a(n)$$$ for a given $$$n$$$? Nah, that's too easy. Solve the "inverse" problem: given $$$x$$$, find $$$n$$$, such that $$$a(n) = x$$$? That's trivial too.

For two given integers $$$x$$$ and $$$y$$$ find the minimum $$$n$$$, such that $$$a(n) = x$$$ and $$$a(n + 1) = y$$$.

The input contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^{18}$$$).

If such $$$n$$$ does not exist, print $$$-1$$$. Otherwise, print the minimal required $$$n$$$. Because the answer can be huge, print it modulo $$$999\,999\,001$$$.

3 1

6

5 7

21

6 2

-1