当前没有测试数据。

细胞计算

题目描述

从前有一种细胞，它的增殖方式很奇怪，经过研究，科学家们找到了一个公式来计算其数量：

$$a_{n}=\begin{cases}xa_{n-1}+n,&n>1\\1,&n=1\end{cases} $$

由于这个数字可能非常大，科学家们只打算知道$a_{n} \bmod w$的值。

输入格式

一行三个正整数$n$，$x$，$w$。

输出格式

一行一个非负整数，表示$a_{n} \bmod w$的值。

数据范围与提示

对于$100\%$的数据，$1 \leq n < 2^{63}$，$1 \leq x$，$w < 2^{31}$。

样例

2 2 47

4

见cell2.in

见cell2.out