模幂计算

难度：T2

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

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

题目描述

给定底数 $a$ 、非负整数指数 $b$ 和正整数 $m$ ，求 $a^b$ 对 $m$ 的标准非负余数。规定任何底数的零次幂为 $1$ ，包括 $0^0$ 。

输入整数 $a$ 、非负指数 $b$ 、正整数 $m$ ；约定 $a^0=1$ ，包括 $a=0$ 。

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

输出 $a^b$ 的模 $m$ 标准余数。

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

3 13 100