#506. 「LibreOJ β Round」ZQC 的作业

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yanQval

题目描述

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

输入格式

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

输出格式

一行一个整数表示答案。

样例

样例输入 1

2 3 5

样例输出 1

3

样例输入 2

4 1 15

样例输出 2

4