J. Ceizenpok’s formula

time limit per test

2.0 s

memory limit per test

256 MB

input

standard input

output

standard output

Dr. Ceizenp'ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery — the Ceizenpok’s formula. This formula has only three arguments: n, k and m, and its value is a number of k-combinations of a set of n modulo m.

While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

Input

Single line contains three integers n, k, m, separated with spaces (1 ≤ n ≤ 10¹⁸, 0 ≤ k ≤ n, 2 ≤ m ≤ 1 000 000).

Output

Write the formula value for given arguments n, k, m.

Examples

Input

2 1 3

Output

2

Input

4 2 5

Output

1

 

 

 

【题解】

裸的扩展lucas + CRT,推荐博文http://blog.csdn.net/clove_unique/article/details/54571216

因为特殊情况k = 0的时候，我以为是0，加了个特判，结果应该是1，不用特判。。。。。。。。。。卡了我半个晚上

1 #include 
           
             2 #include 
            
              3 #include 
             
               4 #include 
              
                5 #include 
               
                 6 #include 
                
                  7 #include 
                 
                   8 #include