异或划分计数

题目描述

Y 同学和他的对手正在玩一个基于 Nim 游戏的变种。游戏初始时共有 $N$ 个石子。

游戏分为两个阶段：

1. 准备阶段：

   • 首先，对手从 $N$ 个石子中取出 $P$ 个，作为第一堆石子放置在场上。
   • 接着，Y 同学将剩余的 $K = N - P$ 个石子分成若干堆（至少一堆，每堆数量任意），记这些堆的石子数分别为 $h_1, h_2, \dots, h_m$。

2. Nim 对战阶段：

   • 此时场上共有 $m+1$ 堆石子，数量分别为 $P, h_1, h_2, \dots, h_m$。
   • 两人遵循标准的 Nim 游戏规则进行博弈：对手先手，Y 同学后手。两人轮流从任意一堆中取走至少一个石子，取走最后一个石子的人获胜。

Y 同学希望在准备阶段通过合理的分堆策略，确保自己能在随后的 Nim 游戏中必胜（假设双方都采取最优策略）。

根据 Sprague-Grundy 定理，作为后手的 Y 同学获胜的充要条件是场上所有堆的石子数量的按位异或和为 $0$，即：

你的任务是计算，有多少种本质不同的分堆方案，使得 Y 同学能够获胜。 两种分堆方案被认为是本质不同的，当且仅当它们构成的石子堆大小的多重集不同（即不考虑堆的顺序）。

由于答案可能很大，请输出方案数对给定的整数 $M$ 取模的结果。

输入格式

输入仅一行，包含三个整数 $N, P, M$。

• $N$：石子总数。
• $P$：对手取走的第一堆石子数。
• $M$：取模的模数。

输出格式

输出一个整数，表示 Y 同学获胜的分堆方案数对 $M$ 取模的结果。

样例

样例输入 #1

8 3 1000

样例输出 #1

2

样例输入 #2

5 2 1000

样例输出 #2

0

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le P < N \le 500$
• $2 \le M \le 10^9$