P4345 [SHOI2015] Super Particle Cannon · Modified

The inventor SHTSC, who once created the Brain-hole Therapy Device and the Super Particle Cannon, has now unveiled his new invention: Super Particle Cannon · Modified — a mysterious device that can fire particle streams with much greater power. Compared with the Super Particle Cannon, Super Particle Cannon · Modified has a fundamental increase in power. It has two parameters $n, k$. It fires, at each position $i$ numbered from $0$ to $k$ inclusive, a particle stream with power $C_{n}^{i} \bmod 2333$. Now SHTSC gives you the parameters of his Super Particle Cannon · Modified. Please compute the remainder modulo $2333$ of the sum of the powers of the particle streams it fires.

The first line contains an integer $t$ denoting the number of test cases. Then follow $t$ lines. Each line contains two integers $n, k$, as described above.

Output $t$ lines. Each line contains one integer: the value of the sum of the powers modulo $2333$.

For $10\%$ of the testdata, $t = 1$, $n, k \le 1000$. For $30\%$ of the testdata, $t = 1$, $n, k \le 1000000$. For $50\%$ of the testdata, $t = 1$, $n \le 10^{18}$, $k \le 1000$. For $70\%$ of the testdata, $t = 100$, $n, k \le 10^{18}$. For $100\%$ of the testdata, $t = 100000$, $n, k \le 10^{18}$. Translated by ChatGPT 5