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:
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$$$.
| Subtask | Points | Constraints |
| 1 | 15 | $$$x, y \le 6$$$ |
| 2 | 22 | $$$x, y \le 20$$$ |
| 3 | 34 | $$$x, y \le 10^6$$$ |
| 4 | 29 | $$$x, y \le 10^{18}$$$ |
3 1
6
5 7
21
6 2
-1