P6130 Random Red Packets

The problem setter is going to send a WeChat red packet to some people, and he is curious about how to randomly distribute the money inside.

There is $1$ yuan in the setter’s red packet, and he wants to randomly split this $1$ yuan among $n$ people. To make it random, he designed the following algorithm to distribute it (in pseudocode): ``` a[0]=0,a[n]=1 for i=1 to n-1 do{ a[i]=rand() } sort(a) for i=1 to n do{ money[i]=a[i]-a[i-1] } ``` Here, the function `rand()` returns a real number uniformly at random in $[0,1]$, and the function `sort()` sorts an array in increasing order. Now, the setter wants to know the expected value of the amount received by the person who gets the $k$-th smallest amount. Since he wants to use this value to estimate how many red packets to send, he will ask you $T$ queries. To avoid precision loss, output the answer modulo $998244353$. To avoid excessive output, output the XOR sum of all answers.

**This problem contains multiple test cases**. The first line contains an integer $T$, the number of test cases. For each test case, one line contains two integers $n, k$.

Output one integer in a single line, representing the XOR sum of the answers to all queries.

**[Sample Explanation]** For the first query, $n=k=1$, so the answer is $1$. For the second query, the larger amount is uniformly distributed on $[\dfrac{1}{2},1]$, and its expectation is $\dfrac{3}{4}$, which becomes $249561089$ after taking modulo. For the third query, the smaller amount is uniformly distributed on $[0,\dfrac{1}{2}]$, and its expectation is $\dfrac{1}{4}$, which becomes $748683265$ after taking modulo. The XOR sum is $574619649$. ------ **[Constraints]** **This problem uses bundled testdata**. $\text{Subtask 1 (4 pts)}$: $n \le 10$, $k=1$. $\text{Subtask 2 (16 pts)}$: $n \le 5 \times 10^3$. $\text{Subtask 3 (20 pts)}$: $k=1$. $\text{Subtask 4 (28 pts)}$: $n \le 10^5$. $\text{Subtask 5 (32 pts)}$: no additional constraints. For $100\%$ of the testdata, $1 \le k \le n \le 10^7$, $1 \le T \le 2 \times 10^5$. Translated by ChatGPT 5