[POI2003] Trinomial
题目描述
求 $(x^2+x+1)^n$ 的第 $i$ 项系数。
输入输出格式
输入格式
第一行一个数 $k$ 表示数据的组数。
接下来的 $k$ 行,每行两个整数 $n,i$。
输出格式
对于每组数据,输出 $x_i \bmod 3$ 之后的结果。
输入输出样例
输入样例 #1
5
2 0
7 4
4 5
5 3
8 15
输出样例 #1
1
2
1
0
2
说明
对于 $100\%$ 的数据,$1 \le k \le 10000$,$0\le n\le 10^{15}$,$0\le i\le 2\times n$。