Description
蛋糕上次做了許多蛋糕(可以吃的)分給大家吃，而許多修課同學也成功的計算出最後會剩下多少片蛋糕。而紅線這次也決定效法蛋糕，綁了一大堆中國繩結，準備平均送給能解出這題的人。現在，假設紅線綁了B^(P^Q)條繩結，並且有M位同學成功的解出了這題，請你幫紅線算一算，最後會剩下多少條中國繩沒有被送出去。
Hint:
先求出B^i與M之間的循環節長度與餘數表。
再求出P^Q是該餘數表中的第n項即為答案。
Example: (以第二組測資3 5 2 5為例)
(3^(5^2))%5=(3^25)%5=(3^(25%4))%5=(3^1)%5=3
Input
輸入會有多組測資，每組測資一行。
每行有四個數字，分別代表B,P,Q,M。
1<=B,P,Q<=2147483647，1<=M<=4000。
為了方便大家計算，gcd(B,M)=1，所有的循環節均從第一項開始。
Output
每筆測資輸出一行，輸出剩下幾條繩結沒有被送出去。(請參考Sample output)