Summation of GCD Powers Modulo p

Given two positive integers n and p, compute the value of the following double summation:

$$ \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j} $$

Since the result might be very large, output the value modulo p.

inputFormat

The input consists of a single line containing two space-separated integers: n and p.

outputFormat

Output a single integer, which is the value of the double summation modulo p.

sample

1 100

1