来源：ICPC 2023–2024 Northwestern Russia Regional Contest（St Petersburg，2023-11-05）

G. 尼姆游戏（）

• 时间限制： 2 秒
• 内存限制： 1024 MB
• 难度估计： CF 2200–2300

题目描述

Georgiy 和 Gennady 发明了一个基于经典 Nim 游戏的新游戏。游戏共有 $n$ 颗石子，分为两个阶段。

在设置阶段：

1. Georgiy 选择一个正整数 $p<n$，并在游戏区域中放置一堆大小为 $p$ 的石子；
2. Gennady 将剩余的 $n-p$ 颗石子划分成任意数量的石堆，每堆大小均为正整数，并且使用完所有剩余石子。

随后进入 Nim 阶段。两人轮流操作，由 Georgiy 先手。每次操作必须从某一堆中取走至少一颗石子，也可以取走该堆中的任意多颗石子。取走最后一颗石子的人获胜。

在设置阶段中，Georgiy 已经放好了大小为 $p$ 的石堆，而 Gennady 尚未划分剩余的 $n-p$ 颗石子。

你需要计算：Gennady 有多少种划分方式，可以使他在双方均采用最优策略时获胜。

根据 Sprague-Grundy 理论，Gennady 获胜当且仅当所有石堆大小（包括 Georgiy 的那一堆）的按位异或和为 $0$。

答案可能很大，请对 $m$ 取模。

若两种方案对应的石堆大小多重集合不同，则认为它们不同；石堆的排列顺序不影响方案，即顺序不计。

输入格式

输入一行三个整数 $n,p,m$，分别表示石子总数、Georgiy 所选石堆的大小和模数：

输出格式

输出 Gennady 获胜的划分方案数对 $m$ 取模后的结果。

样例 1

8 3 1000

2

样例 2

5 2 1000

0

样例说明

在第一个样例中，Gennady 需要划分剩余的 $5$ 颗石子，恰有两种获胜方案：

• 一堆 $3$ 颗石子和两堆 $1$ 颗石子；
• 一堆 $2$ 颗石子和三堆 $1$ 颗石子。

在第二个样例中，无论如何划分剩余的 $3$ 颗石子，Gennady 都必败。