The Formula Sicheol Loved

Q1. How do you put an elephant in a refrigerator?

A1. You make a graduate student do it.

Q2. How do you find the value of a formula?

A2. You make a graduate student do it.

Sicheol, the best graduate student in Yeonhui-dong, expanded formulas the way the Han River flows, and the way he finished them was like an ocean.

Sicheol, who stole the hearts of people all over the world with his brilliant formula expansions, eventually caught the eye of a professor who loved formulas.

$\displaystyle\sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n \mathrm{gcd}\left(i,j\right)\times\mathrm{lcm}\left(i,j\right)$

$\displaystyle\sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n \mathrm{gcd}\left(i,j\right) \times \displaystyle\sum_{n=1}^N \sum_{i=1}^n \sum_{j=1}^n\mathrm{lcm}\left(i,j\right)$

The professor wanted to know the values of the two formulas, but it was not easy. So the professor asked Sicheol to find the values of the two formulas.

At first Sicheol began expanding the formulas reluctantly, but in the end he came to love the two formulas because of the professor.

However, Sicheol was too busy preparing his graduation thesis, so he dumped the rest on Minsu, a fellow graduate student. Minsu thought the values of the two formulas could be large, so he plans to tell the professor the remainders when the values are divided by $K$.

Let us find the values of the two formulas together with Minsu.

The input is given as follows.

$N$ $K$

On the first line, print the value of the first formula.

On the second line, print the value of the second formula.

The values can be large, so print the remainders when they are divided by $K$.

• $1 \leq N \leq 10^6$
• $10^6 \leq K \leq 10^9+7$, $K$ is prime
• All numbers in the input are integers.

Minsu, who caught the professor's eye, went on to a doctoral program with him.