e-olymp
Competitions

Summer School 2011 in Sevastopol, Day 3

Sum of squares

We denote byU(n)the total numberof sequences,consisting onlyof the numbers 1and2, the sumof whose membersis equal ton.

Our task,for a given n (1n 1018) to determine thesum of the squaresof numbersU(n) for all n = 1, …, n. The results aremodulo1000000009.

Input

One numbern.

Output

Print the answer to the problem.

Time limit 1 second
Memory limit 64 MiB
Input example #1
1
Output example #1
1