# Grox的序列五A

- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 你相信些什么？你愿意为这样的信念做出什么样的牺牲？你愿意为了一种直觉、一时念头，还是死去数千年之久的先知话语而甘冒自身或整个种族的危险？
>
> ——科学之书1（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

在你的不懈努力下，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

### 输入

```text
10 103 10007
```

### 输出

```text
5367
```

### 样例 2

### 输入

```text
10 0 10007
```

### 输出

```text
1023
```

### 样例 3

### 输入

```text
3 1 8
```

### 输出

```text
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% | 无额外条件 |