20940번 - 시철이가 사랑한 수식

문제

Q1. 코끼리를 냉장고에 넣는 방법은?

A1. 대학원생을 시킨다.

Q2. 수식의 값을 알아내는 방법은?

A2. 대학원생을 시킨다.

연희동 최고의 대학원생 시철이는 마치 한강이 흐르듯 수식을 전개하고, 그 끝마침이 대양과도 같았다.

화려한 수식 전개로 전 세계인의 마음을 훔치던 시철이는, 어느덧 수식을 사랑하는 교수님의 눈에 띄게 되었다.

$$ \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) $$

교수님은 두 식의 값을 알고 싶었지만 쉽지 않았다. 그래서 교수님은 시철이에게 두 식의 값을 구해 달라고 부탁했다.

처음에 시철이는 마지못해 수식을 전개하기 시작했지만, 결국 교수님 때문에 두 식을 사랑하게 되었다.

하지만 시철이는 졸업논문 준비로 너무 바빴고, 본인의 대학원 동기 민수에게 나머지를 떠넘겼다. 민수는 두 식의 값이 클 수 있다고 생각해, 값을 $K$로 나눈 나머지를 교수님께 알려주려고 한다.

민수와 함께 두 식의 값을 구해보자.

입력

다음과 같이 입력이 주어진다.

출력

첫째 줄에 첫 번째 식의 값을 출력한다.

둘째 줄에 두 번째 식의 값을 출력한다.

값이 클 수 있으니 $K$로 나눈 나머지를 출력한다.

제한

• 1ドル \leq N \leq 10^6$
• 10ドル^6 \leq K \leq 10^9+7,ドル $K$는 소수
• 입력으로 주어지는 모든 수는 정수다.

노트

교수님의 눈에 띈 민수는 박사 과정까지 함께했다.