Description:


小Q有一个集合 \(S\) ,它的元素个数 \(|S|=n\)
对于 \(S\) 的任意一个子集合 \(T\) ,定义 \(f(T)=|T|^k\) ,定义 \(T\) 关于 \(S\) 的补集为 \(S-T\)
小Q想知道,如果他等概率地选择一个 \(S\) 的子集 \(T\) ,那么 \(f(T)-f(S-T)\) 的方差是多少。
由于这个方差值可能很大,不妨设其为 \(v\) ,你只需要给出 \((v\cdot 2^n)\mod m\) 的值即可。

期望和方差的定义可以参见:期望值百度百科 & 方差百度百科

Input:


第一行一个正整数 \(n\) ,满足 \(k \le n \le 10^{10^6}\)
第二行一个正整数 \(k\) ,满足 \(1 \le k \le 10^6\)
第三行一个正整数 \(m\) ,其中 \(m\) 是质数,满足 \(2 \le m \le 10^6\)

Output:


共一行,答案乘 \(2^n\)\(m\) 的值。

Sample Input:


Sample Output:


题解:


估计这是我做过的最难的组合题了( ̄▽ ̄)"

首先可以发现共有 \(2^n\) 种选取 \(T\) 的方案,所以 \(v = \frac{\sum (x-\overline{x})^2 }{2^n}\)

根据对称性可知 \(\overline{x} = 0\) ,所以最后要求的即是 \(\sum x^2\) ,枚举 \(x\) 的大小,可知:

\[ Ans = \sum_{i = 0}^n \binom{n}{i} [i^k - (n-i)^k]^2 \mod m\]

接下来就是没人性的转化。

根据Lucas定理, \(\binom{n}{i} \equiv \binom{\lfloor \frac{n}{m} \rfloor}{\lfloor \frac{i}{m} \rfloor} \binom{n \mod m}{i \mod m} \pmod m\) ,所以当 \(i\mod m > n \mod m\) 时,整个组合数就等于0,所以我们可以对 \(n\) 分块,然后省去 \(i\mod m > n \mod m\) 的部分。

具体的:

可以看出 \(\lfloor \frac{n}{m} \rfloor\ mod\ (m-1) = \frac{n-n\ mod\ m}{m}\ mod\ (m-1)\) ,而 \(m\)\(m-1\) 下的逆元等于 \(1\) ,于是可以轻松求得 \(2^{\lfloor \frac{n}{m} \rfloor\ mod\ (m-1)}\) ,然后我们可以用线性筛求得整数的 \(k\) 次方,整个问题就可以 \(O(\log n+\log k+m)\) 解决。