#P1440. Math

Math

题目描述

给定 n,x,pn,x,p,求 ∑k=1nkx×xk(modp)\sum_{k=1}^n k^x\times x^k\pmod p 的值。

输入格式

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

输出格式

一行一个整数表示答案。

3 4 1000
444

数据规模与约定

对于 30%30\% 的数据,1≤n≤1051\leq n\leq 10^5。

对于 100%100\% 的数据,1≤n,p≤2×1091\leq n,p\leq 2\times 10^9,1≤x≤501\leq x\leq 50。