#GYM104787B. Yet Another Subsequence Problem
Yet Another Subsequence Problem
Description
For any two positive integers $a$ and $b$, define the function by the following C++ code:
std::string gen_string(int64_t a, int64_t b) {
std::string res;
int64_t ia = 0, ib = 0;
while (ia + ib < a + b) {
if ((__int128)ia * b <= (__int128)ib * a) {
res += '0';
ia++;
} else {
res += '1';
ib++;
}
}
return res;
}
$ia$ will equal $a$ and $ib$ will equal $b$ when the loop terminates, so this function returns a bitstring of length $a+b$ with exactly $a$ zeroes and $b$ ones. For example, $gen\_string(4,10)=01110110111011$.
Given the argument of $A, B$, you should calculate the number of different subsequences of $gen\_string(A, B)$, and print it modulo $998244353$.
NOTE: A sequence $a$ is a subsequence of a string $b$ if $a$ can be obtained from b by deleting several (possibly, zero or all) elements.
The first line contains $T\ (1\le T\le 100)$, the number of independent test cases.
Each of the next lines contains two integers $A$ and $B$ ($1\le A,B \le 10^{18}$).
Output the number of different subsequences of $gen\_string(A, B)$ modulo $998244353$.
Input
The first line contains $T\ (1\le T\le 100)$, the number of independent test cases.
Each of the next lines contains two integers $A$ and $B$ ($1\le A,B \le 10^{18}$).
Output
Output the number of different subsequences of $gen\_string(A, B)$ modulo $998244353$.
6
1 1
3 5
4 7
8 20
4 10
27 21
18
5 9
23 30
820 483
5739 9232
86494 55350
606 13336
2768848 1124639
47995594 66053082
1069395 7177
7801842511 4390103762
47882886553 82678306054
193410894 6189355686
51594638 19992922190
59 110
422735115778072 658356435030265
9125338158530266 5328357177709583
60743352262021049 95595862538791630
629312141725417942 999581828389011547
4
70
264
196417
609
667131122
988
220693002
133474535
202371605
778839228
282057418
935955056
943144752
409056617
627433544
578769776
917438628
24364208
109943645
352575425
68058533
402004723
894026897