King Sam is known for his intelligence. To test him, Minister Mistry gave him a question. Now, he needs your help to solve the question and prove himself before Minister Mistry. The question goes like this,

F(n,k,m) = ($\sum\limits_{i = 1}^n \sum\limits_{j = 1}^ij^k$) % m

Constraints :

1 <= n <= 10^18

1 <= k <= 10^18

1 <= m <= 10^6

Input Format:

Input file consists of a single line which contains 3 integers n, k, m.

Output Format:

Output F(n,k,m).