给出 T 次询问，每次给出 n,m，请求出 \binom{n}{m} 对 100,019 取模的结果。

其中 \binom{n}{m} 为二项式系数，它的另一种写法是 C_n^m。

输入的第一行是两个整数，分别表示询问的次数 T 和所给出 n 的最大值 N。  

接下来 T 行，每行两个整数，依次表示给出的 n 和 m。

为了避免输出过大，请你输出一行一个整数，表示所有询问的结果的**按位异或和**。

样例 1 解释

三组询问的答案依次是 1, 6, 10。

数据规模与约定

对 40\% 的数据，保证 1 \leq T \leq 5 \times 10，0 \leq m \leq n \leq 5 \times 100。

对 100\% 的数据，保证 1 \leq T \leq 5 \times 10^4，0 \leq m \leq n \leq N \leq 5 \times 10^4。