Recursion and Mod

Functon f is defined as: f(n) = 3*f(n-1)+4 and f(1) = 1

That is,

f(2) = 3*f(1)+4 = 3*1+4 = 7

f(3) = 3*f(2)+4 = 3*7+4 = 25

f(4) = 3*f(3)+4 = 3*25+4 =79

...

Given an integer n, please calculate the reminder of f(n) divided by 10^9+9, i.e., f(n) mod (10^9+9).

Input

Each test case is on a line, containing only one integer, n, where 0 < n < 2^63. The number of test cases is smaller than or equal to 1000. The input is terminated by end-of-file (EOF).

Output

For each test case, output the reminder of f(n) divided by 10^9+9, i.e., f(n) mod (10^9+9), on a separate line.