$\ \ \ \ $Lcomyn 是个很厉害的选手,除了喜欢写17kb+的代码题,偶尔还会写数学题.他找到了一个数列:
$f_n=\left\{\begin{matrix}
1 ,&n=1 \\
a^b,&n=2 \\
a^bf_{n-1}^cf_{n-2},&otherwise
\end{matrix}\right.$
$\ \ \ \ $他给了你几个数:$n$,$a$,$b$,$c$,你需要告诉他$f_n$模$p$后的数值.
$\ \ \ \ $第一行一个数T,为测试数据组数.
$\ \ \ \ $每组数据一行,一行五个正整数,按顺序为$n$,$a$,$b$,$c$,$p$.
$\ \ \ \ 1\le T \le 10,1\le n\le 10^{18}$,$1\le a,b,c\le 10^9$,p是质数且$p\le 10^9+7$.
$\ \ \ \ $对每组数据输出一行一个数,输出$f_n$对$p$取模后的数值.
1 5 3 3 3 233
190