题目描述

请计算$(a^1+a^2+a^3+ ...... +a^n)\ mod\ 1234567$ 的结果。

输入格式

第一行 $T$，表示数据组数。 接下来的 $T$ 行，每行包含 $a$ 和 $n$，表示一组数据。

输出格式

对于每组数据，输出对应的答案。

样例数据

5 
1 7 
3 10 
5 8 
9 20 
17 100

7 
88572 
488280 
696766 
550479

数据范围

$T < 2000$

$0 < a, n < 2^{31}$