Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3881
From ABC Conjecture

Time Limit: 20 Seconds      Memory Limit: 131072 KB

The abc conjecture (also known as Oesterlé–Masser conjecture) is a conjecture in number theory, first proposed by Joseph Oesterlé (1988) and David Masser (1985) as an integer analogue of the Mason–Stothers theorem for polynomials. The conjecture is stated in terms of three positive integers, a, b and c (hence the name), which have no common factor and satisfy a + b = c. If d denotes the product of the distinct prime factors of abc, the conjecture essentially states that d is usually not much smaller than c. In other words: if a and b are composed from large powers of primes, then c is usually not divisible by large powers of primes. The precise statement is given below.

If a, b, and c are coprime positive integers such that a + b = c, it turns out that "usually" c < rad(abc). rad(n) denotes the product of the distinct prime factors of n. The abc conjecture deals with the exceptions. Specifically, it states that:

    ABC Conjecture. For every ε > 0, there exist only finitely many triples (a, b, c) of positive coprime integers, with a + b = c, such that

c > rad(abc)1+ε

An equivalent formulation states that:

    ABC Conjecture II. For every ε > 0, there exists a constant Kε such that for all triples (a, b, c) of coprime positive integers, with a + b = c, the inequality

c < Kε ⋅ rad(abc)1+ε

The abc conjecture has already become well known for the number of interesting consequences it entails. Many famous conjectures and theorems in number theory would follow immediately from the abc conjecture. Goldfeld (1996) described the abc conjecture as "the most important unsolved problem in Diophantine analysis".

Whatever, our problem is not related to the abc conjecture, it's about the notation rad(n). rad(n) also denotes the largest squarefree number dividing n. The sequence rad(n) can be found as A007947 on OEIS. Most of you know the Euler totient function well. The Euler totient function φ(n) denotes the number of integers which is coprime to n and not greater than n. It is A000010 on OEIS. In this problem, f(n) denotes rad(n)×φ(n÷rad(n)). And g(n) denotes the Dirichlet convolution of the function f and 1. In other words, g(n) is sum of f(d) which d is the divisor of n. In math notation, g(n)=Σd|n f(d). And your task to calculate the partial sum of g(n). That is to say, given you an integer N, you should calculate the sum of g(1), g(2), ... , g(N).


There are multiple cases. Each case is an integer number N in a line. (1≤ N≤ 1012)


Print the sum of g(1), g(2), ... , g(N) in one line each case. Because the result may be very large, print it modulus 109+9.

Sample Input


Sample Output



abc conjecture, From Wikipedia
Author: ZHOU, Yuchen
Source: ZOJ Monthly, July 2015
Submit    Status