505013 - 扩展卢卡斯定理

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

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

Input

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

Output

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

Examples

Input

  5 3 3

Output

1

Input

666 233 123456

Output

61728
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题