cache = {}

mod = 1000000009

def ans(n):
    if cache.has_key(n):
        return cache[n]

    if n == 0:
        cache[n] = 1
        return cache[n]
    if n == 1:
        cache[n] = 10
        return cache[n]

    temp1 = ans(n/2)
    temp2 = ans(n/2-1)

    if (n & 1) == 0:
        cache[n] = (temp1*temp1 - temp2*temp2) % mod
    else:
        temp3 = ans(n/2 + 1)
        cache[n] = (temp1 * (temp3 -temp2)) % mod

    return cache[n]

print ans(1000000000)