Prime Power Sum Summation

Given an integer ( N ), let ( S(n) ) denote the sum of the ( k )-th powers of all prime numbers less than or equal to ( n ), i.e., [ S(n) = \sum_{p \le n,\ p \text{ is prime}} p^k ]

You are to compute the value of [ \sum_{i=1}^{\lfloor\sqrt{N}\rfloor} i^2 \cdot S\Bigl( \Bigl\lfloor \frac{N}{i} \Bigr\rfloor \Bigr) \pmod{p}, ] where the final result is taken modulo a given prime ( p ).

inputFormat

The input consists of three space-separated integers:

( N ): the main parameter, ( k ): the exponent used in the prime power sum ( S(n) ), and ( p ): a prime number used as the modulus.

It is guaranteed that ( p ) is a prime.

outputFormat

Output a single integer which is the computed result of the summation modulo ( p ).

sample

10 1 1000000007

102