前n项幂的余数和

题目描述

给定 a、n、m，求 (a^1+a^2+…+a^n) mod m。n=0时为空和。

输入格式

一行输入 a、n、m，满足 0≤a≤10^9、0≤n≤10^18、1≤m≤2×10^5。

输出格式

输出幂和的标准余数；n=0时输出0。

样例

输入

2 2026 7

输出

2