T446080 百战名

>将军**百战**身**名**裂。向河梁、回头万里，故人长绝。 > >易水萧萧西风冷，满座衣冠似雪。 > >——宋·辛弃疾[《](https://b23.tv/4KlBGaF)贺新郎·别茂嘉十二弟[》](https://hanyu.baidu.com/shici/detail?pid=885dda910b4647f08f0a0f922f67f51e&tn=sug_click)

百战磨砺，方成大将。 对于一位将军来说，每次作战都会使经验值乘以 $x_1$，名声值乘以 $x_2$，其中 $x_1,x_2$ 分别是 $ax^2+bx+c=0$ 的两根且 $x_1\leq x_2$。$a,b,c$ 均由将军自身的能力决定，在本题中可看作常数。 将军未经战事，未试锋芒时，**经验值和名声值均为 $1$**。请你求出经过 $n$ 次作战后这位将军的经验值与名声值之和，由于答案可能很大，需要对 $p$ 取模。 形式化地，给出 $a,b,c,p$，设 $x_1,x_2$ 为方程 $ax^2+bx+c=0$ 的两根，求 $(x_1^n+x_2^n) \mod p$ 的值。

第一行四个整数 $a,b,c,p$ 第二行一个整数 $n$，含义均如上所述。

一行一个整数，表示模 $p$ 后的答案。

**本题开启捆绑测试，且所有数据捆绑为同一个 Subtask。** 对于所有数据，$b^2 - 4ac \ge 0,1 \le a,b,c \le 10^9,0\le n \le 10^{18},p \le 10^9+7$，$p$ 为质数且保证存在逆元。