时间限制：1秒　　内存限制：256M

---

【问题描述】

　　请你计算 \((a^1+a^2+⋯+a^n )\ mod\ 1234567\) 的结果。

【输入格式】

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

【输出格式】

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

【输入输出样例1】

　Input

5
1 7
3 10
5 8
9 20
17 100 

　Output

7
88572
488280
696766
550479

【数据限制】

　　\(T ≤ 1000\)
　　\(0 < a , n < 2^{31}\)

【来源】

　ITer