Logo Universal Online Judge

UOJ

时间限制:4 s 空间限制:1024 MB
统计

【题目描述】

记在 $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$ 是质数。

大颜例