P2344[模板]组合数取模·扩展卢卡斯 | ||
|
问题描述
计算
\[
C_n^k\mod m
\]
输入格式
输入三个整数$n,k,m$
输出格式
输出计算结果
样例输入
样例输入1:
50 30 49
样例输入2:
50 30 64
样例输入3
50 30 10007
样例输入4
50 30 31381952
样例输出
样例输出1:
0
样例输出2:
56
样例输出3:
2551
样例输出4:
16404024
提示
\(n,k,m\leq 10^{18}\),保证$m$分解质因数后每个质数的次方都不超过$10^6$