#P1630. 求和

求和

题目描述

1b+2b++ab1^b+2^b+\cdots + a^b 的和除以 10410^4 的余数。

输入格式

本题有多组数据。

第一行一个整数 NN,表示共有 NN 组测试数据。

对于每组数据,一行两个整数 a,ba,b

输出格式

对于每组数据,一行一个整数,表示答案。

1
2 3
9

提示

对于 30%30\% 的数据,N10N \le 10a,b103a,b \le 10^3

对于 100%100\% 的数据,1N1001 \le N \le 1001a,b1091 \le a,b \le 10^9