幂式差的校验值

难度：T2

【知识点：快速幂与基础模运算】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

给定两组底数与指数，求幂之差 $a^b-c^d$ 对 $m$ 的标准非负余数，结果必须在 $0$ 到 $m-1$ 之间。

输入格式

输入$a$、$b$、$c$、$d$、$m$，约定任意底数的$0$次幂为$1$。

规则说明

对正整数 $m$ 取标准余数，是取满足 $0\le r<m$ 的整数 $r$，使原数减去 $r$ 后能被 $m$ 整除。即使原数为负，结果也不能为负；例如 $-2$ 对 $5$ 的标准余数是 $3$。

输出格式

输出($a^b-c^d$)对$m$的标准非负余数。

数据范围

|$a$|,$|c|\le 10^9$，$0\le b,d\le 10^18$，$1\le m\le 10^9$。

样例输入

-5 0 2 11 1

样例输出

0

样例输入 2

2 3 3 2 7

样例输出 2

6

样例说明 2

两个幂之差是 $8-9=-1$；它对 $7$ 的标准非负余数是 $6$，不是负数。