题目名称

「SHOI2015」超能粒子炮·改

题目描述

发明家SHTSC发明了超能粒子炮·改，该装置有两个参数 $n$、$k$，会向编号为 $0$ 到 $k$（包含两端）的位置 $i$ 发射威力为 $C_{n}^{i} \bmod 2333$ 的粒子流 ，其中 $C_{n}^{i}$ 是组合数。

现在给定参数 $n$、$k$，要求计算发射的粒子流的威力之和除以 $2333$ 所得的余数。

输入格式

• 第一行：一个整数 $t$，表示数据组数。
• 之后 $t$ 行：每行两个整数 $n$、$k$，分别表示题目中的参数。

输出格式

输出 $t$ 行，每行一个整数，为对应组参数下粒子流的威力之和模 $2333$ 的值。

输入输出样例

输入

3
5 5
10 7
1145 14

输出

32
968
763

数据范围与提示

• 对于 $10\%$ 的数据，$t = 1$，$n, k \leq 1000$。
• 对于 $30\%$ 的数据，$t = 1$，$n, k \leq 1000000$。
• 对于 $50\%$ 的数据，$t = 1$，$n \leq 10^{18}$，$k \leq 1000$。
• 对于 $70\%$ 的数据，$t = 100$，$n, k \leq 10^{16}$。
• 对于 $100\%$ 的数据，$t = 100000$，$n, k \leq 10^{18}$ 。