{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"小 $Q$ 有一个集合 $S$ ,它的元素个数 $|S|\u003dn$ 。\r\n对于 $S$ 的任意一个子集合 $T$ ,定义 $f(T)\u003d|T|^k$ ,定义 $T$ 关于 $S$ 的补集为 $S-T$ 。\r\n小 $Q$ 想知道,如果他等概率地选择一个 $S$ 的子集 $T$ ,那么 $f(T)-f(S-T)$ 的方差是多少。\r\n由于这个方差值可能很大,不妨设其为 $v$ ,你只需要给出 $(v\\cdot 2^n)\\bmod m$ 的值即可。\r\n期望和方差的定义可以参见:[期望值 $_$ 百度百科]( $http://baike.baidu.com/view/476035.htm) \\\u0026 [ 方差 _ 百度百科]( http://baike.baidu.com/view/172036.htm)"}},{"title":"Input","value":{"format":"MD","content":"第一行一个正整数 $n$ ,满足 $k \\le n \\le 10^(10^6)$ 。\r\n第二行一个正整数 $k$ ,满足 $1 \\le k \\le 10^6$ 。\r\n第三行一个正整数 $m$ ,其中 $m$ 是质数,满足 $2 \\le m \\le 10^6$ 。"}},{"title":"Output","value":{"format":"MD","content":"共一行,答案乘 $2^n$ 模 $m$ 的值。"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\n1\n23333\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10240\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}