불확정성이 넘쳐흘러

욱제는 대회 참가자들을 괴롭히기 위해 길이 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{와 서로소일 확률} & \text{otherwise} \end{cases}$

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

$\sum_{i=1}^{N}{\sum_{j=1}^{N}{f_Y (i, j)}} = {Z\over Y^N}$

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

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

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