시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 37 18 14 42.424%

문제

욱제는 대회 참가자들을 괴롭히기 위해 길이 N의 특이한 수열을 만들었다! 신기하게도, 이 수열의 원소들은 우리가 들여다보기 전까지는 확률적으로 존재할 뿐이며 여러 자연수들이 중첩된 상태로 존재한다. 이 수열의 원소들을 확정하기 위해서는 관측이라는 특별한 과정이 필요하다. 

자연수 Y ≥2 와 닫힌 구간 [ℓ, r] 에 대해, 관측관측의 결과값이 다음과 같이 정의된다.

수열의 ℓ번째 원소부터 r번째 원소를 각각 A, Aℓ+1, ..., Ar라는 확률변수로 놓자. 어떤 Ai관측하는 순간, Ai 는 닫힌 구간 [1, Y]에 속한 임의의 자연수로 고정되어 Bi가 된다. (어떤 자연수가 고정될 확률은 모두 1/Y로 같다) 관측은 각 원소마다 독립적으로 시행하며, 이를 통해 A, Aℓ+1, ..., Ar에서 B,, Bℓ+1, ..., Br를 얻어낼 수 있다. 관측의 결과값이란 B, Bℓ+1, ... , Br의 최대공약수를 뜻한다. 관측된 원소들은 곧바로 원래 상태로 돌아가 다시 확률적으로만 존재하게 되며, 이후의 관측에 어떠한 영향도 주지 않는다.

욱제는 이 수열을 이용해서 다음과 같은 특이한 함수를 정의했다.

\[f_Y(i, j) = \begin{cases} 0 & \text{if $i > j$} \\ \text{[i, j]를 관측한 결과가 Y와 서로소일 확률 } & \text{otherwise} \end{cases}\]

이때 다음을 만족하는 정수 Z를 구해보자.

\[\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{N}{f_Y (i, j)}} = {Z\over Y^N}\]

Z는 굉장히 커질 수 있으므로, 109 + 9로 나눈 나머지를 구해 출력한다.

입력

첫째 줄에 수열의 길이 N, 자연수 Y가 주어진다. (1 ≤ N ≤ 105, 2 ≤ Y ≤ 109 )

출력

정수 Z를 109 + 9로 나눈 나머지를 출력한다.

예제 입력 1

1 3

예제 출력 1

2

예제 입력 2

3 12

예제 출력 2

5488

출처

University > 숭실대학교 > 2019 SCON B번