#P3823. 定情信物

    ID: 3025 传统题 1000ms 256MiB 尝试: 914 已通过: 200 难度: 6 上传者: 标签>CF2100提高乘法原理组合数乘法递推质因数指数约分批量求逆费马小定理快速幂ByEOLV数据加强by

定情信物

题目描述

nn 维超立方体可看作由 n−1n-1 维超立方体沿垂直于它的所有的棱的方向平移得到的立体图形。 我们可以将点看作 00 维超立方体,将直线看作 11 维超立方体,将正方形看作 22 维超立方体……依此类推。任何一个 nn 维超立方体 (n>0)(n>0) 都是由低维的超立方体元素组成的:它的 n−1n-1 维表面 是 n−1n-1 维的超立方体,它的 n−2n-2 维边缘是 n−2n-2 维的超立方体,它的 n−3n-3 维元素是 n−3n-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\% 的数据,1≤K≤1071\leq K \leq 10^7,pp 为 10910^9 内的素数。