A. Một bài toán nhỏ
Không gì mở đầu câu chuyện tốt hơn miếng trầu - hoặc là một bài toán nho nhỏ.

Những nghệ nhân nick xám Codeforces cho biết, từ thời xa xưa, Vương Hải Thanh đã có lòng đam mê với những bài toán lạ - những bài toán liên quan đến những đôi trai gái tuổi mới lớn... Không hề hão huyền, họ cũng đã đưa cho chúng tôi - những người đi tim huyền thoại - một câu đố mà họ tin do chính huyền thoại T-s-x viết nên. Câu đố như sau:

Cho hai số (n, k). Hãy tính ((k-1)^n + (k-1)(-1)^n) mod 6971.

Input
Dòng đầu tiên ghi số test T (T ≤ 50).
Sau đó là T test, mỗi test gồm 1 dòng ghi 2 số n và k (1 ≤ n, k ≤ 10^9).
Output
Với mỗi test in trên 1 dòng đáp số.

Sample
Input
2 4 4 6 9
Output
84 4225