周期倍率

难度：T2

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

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

题目描述

从初始值 $x$ 开始，每个周期把当前值乘以 $a$，再对 $m$ 取标准非负余数。求 $k$ 个周期后的余数；$k=0$ 时也输出 $x$ 对 $m$ 的标准余数。

输入格式

输入初始值$x$、倍率$a$、周期数$k$、模数$m$。每个周期把当前值乘$a$，再对$m$取标准余数。

规则说明

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

输出格式

输出$k$周期后的标准余数。

数据范围

$0\le x,a\le 10^9$，$0\le k\le 10^18$，$1\le m\le 10^9$。

样例输入

0 1 0 1

样例输出

0

样例输入 2

5 3 2 7

样例输出 2

3

样例说明 2

第一周期得到 $15$ 对 $7$ 的余数 $1$，第二周期得到 $3$。