Easy Sequence Problem

Suppose $(A_N,A_{N+1})=(P,Q)$. If $P<Q$, the last binary bit of $N$ is $0$ and the previous pair is $(P,Q-P)$. If $P>Q$, the last bit is $1$ and the previous pair is $(P-Q,Q)$.

Repeated subtraction can be too slow. When $P<Q$, let $t=\left\lfloor\frac{Q-1}{P}\right\rfloor$ and subtract $tP$ at once; this removes $t$ trailing zero bits. The case $P>Q$ is symmetric. Since $P$ and $Q$ are coprime, the process ends at $(1,1)$.

Reattach the removed bit runs in reverse order. Appending $t$ zeros changes $X$ to $X2^t$, while appending $t$ ones changes it to $X2^t+(2^t-1)$. Work modulo $998\,244\,353$. The number of quotient steps is logarithmic, so the time complexity is $O(\log \max(P,Q))$. Solution written by GPT5.6