505013 - 扩展卢卡斯定理

【题目描述】扩展卢卡斯定理(Exlucas)

求C_n^m mod p的值,其中C为组合数。

输入

一行三个整数n,m,p(1≤m≤n≤10^18,2≤p≤10^6,不保证p是质数)。

输出

一行一个整数,表示答案。

样例

输入

  5 3 3

输出

1

输入

666 233 123456

输出

61728
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题