Stern's Sequence

题号：NC226656
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Stern’s Triangle is similar to Pascal’s Triangle in that some values in each row are the sums of values in the previous row. In this case the previous row values are also copied down:

Row $n$ has $2^{n}-1$ elements $S(n, k)$ . Where:

$S(n, k) = 0$ for $k \leq 0$ or $k ≥ 2^{n}$

$S(1, 1) = 1$

$S(n+1, 2*k) = S(n, k)$ for $n ≥ 1$

$S(n+1, 2*k+1) = S(n, k) + S(n, k+1)$

If we align the $S(n, k)$ values so $S(n+1, k)$ is directly below $S(n, k)$ , we get:

We see that for $n$ sufficiently large, $S(n+1, k) = S(n, k)$ .

The sequence of these limiting values in called Stern’s Diatomic Sequnce:

$b(1), b(2), b(3), …$

It has the property that for every positve rational number, $r$ , there is exactly one value $k$ for which $r = b(k)/b(k+1)$ .

For example: $3 / 5 = b(10 )/ b(11)$

Write a program which takes as input a rational number $p/q$ in lowest terms and outputs the value $k$ for which $p = b(k)$ and $q = p(k+1)$ . This number can get quite large, so out put it modulo the large prime 998,244,353.

输入描述:

Input consists of a single line containing two relatively prime, space separated decimal integers, p and q (1 ≤ p, q ≤ 400000).

输出描述:

The single output line consists ofthe integer k, for which p = b(k) and q = b(k+1) printed modulo 998,244,353.

示例1

输入

复制

3 5

输出

复制

示例2

输入

复制

1234 763

输出

复制