设x_1、x_2满足x²-Sx+P=0，计算T_n=x_1^n+x_2^n对M取模。使用T_0=2、T_1=S、T_n=S·T_(n-1)-P·T_(n-2)。
一行输入整数S、P、非负整数n和正整数M。保证 ∣S∣,∣P∣≤109|S|,|P|\le 10^9∣S∣,∣P∣≤109，0≤n≤10180\le n\le 10^{18}0≤n≤1018，1≤M≤1091\le M\le 10^91≤M≤109。
输出T_n mod M，结果规范到0至M-1。
5 6 4 1000
97
使用您的 星源智一OJ 通用账户
