Let ~f(x, y)~ be the lowest common multiple of ~x~ and ~y~ and ~g(x, y)~ be the greatest common divisor of ~x~ and ~y~. Determine ~\sum_{x=1}^N \sum_{y=1}^N f(x, y) \times g(x, y)^2~ modulo a prime number, ~K~.

Input Specification

The only line will contain two space-separated integers, ~N~ ~(1 \le N \le 10^{10})~ and ~K~ ~(2 \le K \le 2 \times 10^9)~.

Output Specification

Output ~\sum_{x=1}^N \sum_{y=1}^N f(x, y) \times g(x, y)^2~ modulo ~K~.

Sample Input

10 131

Sample Output

64