You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

• zzz给uuu出了道题：
• { 给你a,b,c,d,p,请求出
• $(\dfrac{a^b}{c^d}) \ Mod \ p$
• 假设一定能整除。}
• uuu才学了亿天编程，他一看就懵(hui)了，你能帮他回答出来吗？

Format

Input

a,b,c,d,p

Output

ans

Samples

9 2 3 2 5

4

Limitation

1s, 1024KiB for each test case.$1≤a,b,c,d,p≤10^9, GCD(c, p) = 1$，p是质数，注意时限20ms，std的10倍