17257번 - 불확정성이 넘쳐흘러

문제

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

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

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

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

\[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는 굉장히 커질 수 있으므로, 10⁹ + 9로 나눈 나머지를 구해 출력한다.

입력

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

출력

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

제한

힌트