{"raw_statement":[{"iden":"statement","content":"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.\n\nGiven $a$, $n$, and that $x^2 -a x + 1 = 0$, find $b$ such that $x^(2 n) -b x^n + 1 = 0$.\n\nThe 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.\n\n*Constraints*\n\n$1 <= T <= 10^5$\n\n $| a |, | n | <= 10^(18)$\n\nFor 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.\n\n"},{"iden":"input","content":"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 <= T <= 10^5$ $| a |, | n | <= 10^(18)$"},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of rounds.  \n- For each round $ i \\in \\{1, \\dots, n_k\\} $, let $ (a_i, b_i, c_i) \\in \\mathbb{Z}^3 $ be given with $ a_i, b_i, c_i \\geq 1 $.  \n\nLet $ A_0 = 0 $, $ D_0 = 0 $.  \nFor round $ i $:  \n- $ A_i^- = A_{i-1} + D_{i-1} $ (aggressivity before action)  \n- Choose one of three actions:  \n  1. **Action 1**: Deal $ a_i $ damage, set $ D_i = D_{i-1} + 1 $, $ A_i = A_i^- $  \n  2. **Action 2**: Deal $ b_i $ damage, set $ D_i = D_{i-1} $, $ A_i = A_i^- + c_i $  \n  3. **Action 3**: Deal $ 0 $ damage, set $ D_i = D_{i-1} $, $ A_i = A_i^- $  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10 $  \n2. $ 1 \\leq n_k \\leq 100 $ for each test case  \n3. $ \\sum_{k=1}^T n_k \\leq 100 $  \n4. $ 1 \\leq a_i, b_i, c_i \\leq 10^9 $  \n\n**Objective**  \nMaximize total damage over $ n_k $ rounds:  \n$$\n\\max \\sum_{i=1}^{n_k} \\text{damage}_i\n$$  \nover all valid sequences of actions.","simple_statement":"Rikka has 0 aggressivity and 0 increment at start. In each of n rounds:  \n1. Her aggressivity increases by her increment.  \n2. She chooses one of three actions:  \n   - Add a_i to total damage,  \n   - Add b_i to her increment,  \n   - Add c_i to her aggressivity.  \nFind the maximum total damage she can deal.","has_page_source":false}