题目描述

ZQC 有一道作业题：给定 $ p(1 \leq p < 2 ^ {31}), q(0 \leq q < 2 ^ {31}), n(2 \leq n < 2 ^ {31}) $，求 $ x ^ {p} + q $ 在模 $ n $ 意义下有多少取值。
由于 ZQC 急着去找妹子，所以这道题由你来解决。

输入格式

一行三个整数 $ p, q ,n $。

输出格式

一行一个整数表示答案。

样例 1

input

2 3 5

output

3

样例 2

input

4 1 15

output

4