bzoj#P3823. 定情信物

定情信物

题目描述

nn 维超立方体可看作由 n1n-1 维超立方体沿垂直于它的所有的棱的方向平移得到的立体图形。 我们可以将点看作 00 维超立方体,将直线看作 11 维超立方体,将正方形看作 22 维超立方体……依此类推。任何一个 nn 维超立方体 (n>0)(n>0) 都是由低维的超立方体元素组成的:它的 n1n-1 维表面 是 n1n-1 维的超立方体,它的 n2n-2 维边缘是 n2n-2 维的超立方体,它的 n3n-3 维元素是 n3n-3 维的超立方体……

小 E 对妹子的情意即为在他的定情信物—— KK 维超立方体中含有每一维的元素个数。

由于元素个数可能较大,只需要输出它所包含的每一维元素个数模 pp 后的异或和。

输入格式

一行两个整数 K,pK,p

输出格式

一个非负整数,表示小 E 的定情信物所包含的每一维元素个数模 pp 后的异或和。注意异或和可能会大于 pp

3 7
3
4 2333
33
12 7723
360

样例解释

对于样例 #1,一个三维超立方体含有 88 个零维元素、1212 个一维元素、66 个二维元素、11 个三维

元素,模 77 后分别为 1,5,6,11,5,6,1,异或和为 $1\operatorname{xor} 5\operatorname{xor}6\operatorname{xor}1=3$。

数据规模与约定

对于 100%100\% 的数据,1K1071\leq K \leq 10^7pp10910^9 内的素数。