题目描述

给定 $n,x,p$，求 $\sum_{k=1}^n k^x\times x^k\pmod p$ 的值。

输入格式

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

输出格式

一行一个整数表示答案。

3 4 1000

444

数据规模与约定

对于 $30\%$ 的数据，$1\leq n\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^9$，$1\leq x\leq 50$。