【题目描述】

求1^b+2^b+…+a^b的和除以l0000的余数。

【输入文件】

第一行包含一个正整数N，表示共有N组测试数据；

接下来N行，每行包含两个正整数a和b。

【输出文件】

共N行，每行一个对应的答案。

【样例输入】

1
2 3

【样例输出】

9

【数据规模】

对于30%的数据中，满足N≤10，a,b≤1000；

对于l00%的数据中，满足N≤100，a，b≤1000000000。