e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

April 25 - ADA Contest

Sum of squares

Let U(n) be the total number of sequences, consisting only of 1 and 2, which sum equals to n.

For a given integer n find the sum of the squares of numbers U(i) for all i = 1,..., n. Print the result modulo 109 + 9.

Input

One positive integer n (1n1018).

Output

Print the value of (U(1)^2 + U(2)^2 + ... + U(n)^2) mod 1000000009.

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