Grox的序列五A¶
- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- 参考评测环境与测量
背景故事¶
你相信些什么？你愿意为这样的信念做出什么样的牺牲？你愿意为了一种直觉、一时念头，还是死去数千年之久的先知话语而甘冒自身或整个种族的危险？
——科学之书1（《Spore》，英文资料）
在你的不懈努力下，Grox 终于与你结成了盟友。与此同时，全银河系的其他文明都向你宣战了！
历经数十亿 Spore 年，Grox 终于交到了朋友，对这份友谊倍加珍惜。你发现他们不再像从前那样冰冷：他们也有喜怒哀乐，也会笑。作为礼物，他们构造了一个数列送给你。
整个数列实在太长，你决定计算它的特征数，再把这个特征数送回母星。
形式化问题描述¶
给定非负整数 \(n,k\) 和正整数 \(p\) .定义长度为 \(n+1\) 的数列
\[
a_i=i^k\binom ni\qquad(0\le i\le n)
\]
本题约定 \(0^0=0\) ；其他整数的零次幂为 \(1\) .计算特征数
\[
S=\left(\sum_{i=0}^n a_i\right)\bmod p
\]
输出最小非负余数。\(n\) 以十进制给出，可能无法存入通常的整数类型；\(p\) 不保证为质数。
输入格式¶
一行三个十进制整数 \(n,k,p\) .
输出格式¶
输出一行一个整数 \(S\) .
样例¶
样例 1¶
输入¶
10 103 10007
输出¶
5367
样例 2¶
输入¶
10 0 10007
输出¶
1023
样例 3¶
输入¶
3 1 8
输出¶
4
样例解释¶
样例二中，只有 \(i=0\) 不贡献，答案为 \(2^{10}-1=1023\) .样例三中，求和为 \(3+6+3=12\) ，对 \(8\) 取模得到 \(4\) .
数据范围与保证¶
对 100% 数据：
\(0\le n\le10^{1000}\) ；\(0\le k\le3000\) ；\(1\le p\le2\times10^9\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |