【题目描述】
记在 $m$ 维超空间中放置 $n$ 个 $m − 1$ 维超平面,最多可以将该空间分割成 $f(n, m)$ 个区域。
例如 $f(3, 1) = 4, f(5, 2) = 16$。
求 $\sum\limits_{i=0}^n f(i,m)$, 对一个给定质数 $p$ 取模。
【输入格式】
第一行三个正整数 n, m, p。
【输出格式】
一行一个整数,表示答案对 $p$ 取模后的值。
【样例 1 输入】
5 2 233
【样例 1 输出】
41
【样例 2 输入】
5 3 2333
【样例 2 输出】
56
【样例 3】
见题目目录下的 $dimension3.in$ 与 $dimension3.ans$。
【数据范围】
本题不开启子任务,每个测试点等分。
对于 $10\%$ 的数据,$n, m \le 10$。
对于 $30\%$ 的数据,$n, m \le 10^3$。
对于 $40\%$ 的数据,$n, m \le 10^8$。
对于另外 $10\%$ 的数据,$m \le 10^3$。
对于另外 $20\%$ 的数据,$m \le 10^6$。
对于 $100\%$ 的数据,$1 \le n, m \le 10^{18}, p \le 2 \times 10^7$ 且 $p$ 是质数。