Math(math)
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
求 sigma(i^m)(1<=i<=n)的值，由于该值太大，你只需要输出该值 Mod 10007 的结果。
Format
Input
第一行一个正整数 T，为测试组数。
接下来 T 行，每行两个正整数 n 和 m。
Output
输出共 T 行，每行一个答案。
Samples
1
2 3
9
Limitation
数据范围：
1<=T<=100，1<=n,m<=10^9。
对于 30%的数据,T<=10,n,m<=1000