4566 . 貳零貳參建北電資演算法小社賽 pF - Fermat's Problem
Description
Cjtsai 很電，而 AaW 不會數學
Owing to 模考前 AaW 都在台南吃牛肉湯跟唬爛，所以他數學燒了
In order not to 學測 +365 ，AaW決定開始認真跟 Cjtsai 學數學
However, cjtsai 忙著在聖誕夜修他自己搞壞的 ISCOJ ，沒空理 AaW
Therefore 他隨手把他剛剛証明完的費馬大定理丟給 AaW，要他幫他驗算
Despite the fact that cjtsai 的證明很顯然，但由於紙上空間不太夠，AaW還是看不太懂
Thus, AaW 跑去問佑佑：「教我費馬大定理」
「I consider 小的 to be better than 大的。」佑佑一邊看著國語實小的小弟弟一邊說。
AaW thinks that 佑佑在開車，所以他決定來解決簡單一點的問題。
「There are 總共$B$ 位807或佑佑，已知807有807隻腳，佑佑有2隻腳 ，總共有 $A$ 隻腳，如果一隻佑佑和一隻807可以組成一對 CP，請問最多能同時存在多少對的 CP（假設807和佑佑遵守一夫一夫制）？請輸出答案乘 $k$ 的 $n$ 次方除 $m$ 的餘數($ans*((k ^ n) \% m)$)」
But, AaW還是不會解這題，所以你們要幫他的忙嗎？
Input Format
T
A B n m k
A B n m k
A B n m k
...
- $1 < T < 10 ^ 5$
- $1 < A < 10 ^ 4$
- $1 < B < 10 ^ 4$
- $1 < n < 10 ^ {87} $
- $1 < m < 10 ^ 7$
- $1 < k < 10 ^ 6$
- 其中，n 除以$ [m - (1到m之間所有和m的最大公因數大於1的數的數量)] $ 的商為非負整數且m為質數
- $k \% m \neq 0$
- 記得看部分分
Output Format
輸出一個整數，為答案乘 $k$ 的 $n$ 次方除 $m$ 的餘數
保證答案唯一
Sample Input 1
2 809 2 2 2 1 811 3 2 3 2
Sample Output 1
1 1
Hints
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $t=1$, $ n < 10000 $ | 69 |
| 2 | 0~19 | $ n < 10 ^ {15} $ | 18 |
| 3 | 0~29 | $ 1 < n < 10 ^ {87} $ | 13 |
