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$$$.
61 13 54 78 204 1027 21
4 70 264 196417 609 667131122
185 923 30820 4835739 923286494 55350606 133362768848 112463947995594 660530821069395 71777801842511 439010376247882886553 82678306054193410894 618935568651594638 1999292219059 110422735115778072 6583564350302659125338158530266 532835717770958360743352262021049 95595862538791630629312141725417942 999581828389011547
988 220693002 133474535 202371605 778839228 282057418 935955056 943144752 409056617 627433544 578769776 917438628 24364208 109943645 352575425 68058533 402004723 894026897
| Название |
|---|


