31. 海牛乘法

0 Judge

Code: 0


海牛乘法

題目敘述

海牛想要出一些數學題目給小學生算,基本上他要出的單元是除法。 要寫題目的小學生們正好教到千億以內的除法這個單元,所以海牛要出一些千億以內的數字當作題目。 可是千億有點大,海牛懶得驗算答案所以他想請你幫它算。 不過海牛怕你洩題,所以只會給你$Ai$除以 Mi 的餘數。 請你幫它算出正確答案,也就是 Ai 的 Yi 次方的餘數(對,海牛覺得多乘幾次比較好玩),當然你也只要告訴它答案除以 Mi 的餘數就好了。

輸入說明

第一行會有一個整數 N,代表總共有 N 題題目。 接下來 N 行,第 i 行包含三個正整數 Xi Yi Mi,Xi 是題目 Ai 除以 Mi 的餘數。

保證 $1\leq N \leq 10^4$, $1\leq Xi,Yi\lt Mi$, $3\leq Mi\leq 10^9 + 7$。

輸出說明

每個題目輸出一行,對於第 i 道題目,輸出一個小於 Mi 的非負整數代表答案。 如果你覺得沒有標準答案,請輸出 "SeaCow"。

範例輸入

範例輸出


Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 1