405708: GYM102051 I Nate and Integer Coefficient

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Nate and Integer Coefficienttime limit per test5.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

Nate's math teacher thinks he watches too much anime and not enough time studying for their algebra test. Nate insists that he's already prepared for the test, but in order to prove it, he has to solve the following problem that his teacher gave him.

Given $$$a$$$, $$$n$$$, and that $$$x^2 - ax + 1 = 0$$$, find $$$b$$$ such that $$$x^{2n} - bx^n + 1 = 0$$$.

Input

The first line of input contains a single integer $$$T$$$, the number of test cases. The next $$$T$$$ lines of input each contain two space-separated integers $$$a$$$ and $$$n$$$, respectively, the values in the equation.

Constraints

$$$1 \leq T \leq 10^5$$$

$$$\left|a\right|, \left|n\right| \leq 10^{18}$$$

Output

For each of the $$$T$$$ test cases, output in its own line a single integer, $$$b$$$, that satisfies the equation. Since the answer can get quite large, output only the positive remainder when $$$b$$$ is divided by $$$10^9+7$$$, a prime number. It can be proven that $$$b$$$ is always an integer.

ExampleInput
3
2 1231
2 10000000
5 0
Output
2
2
2

加入题单

上一题 下一题 算法标签: