Everybody knows about Fibonacci, they guy who invented the famous sequence where the first two terms are 0 and 1 and from then on every term is the sum of the previous two.
What most people don’t know is that he had a somewhat mentally retarded brother named Tribonacci. In a desperate attempt to surpass his brother and achieve eternal glory, Tribonacci invented his own sequence: the first three terms are 0, 1, 2 and from then on every term is the sum of the previous three.
Sadly, regardless of enormous courage and dedication, Tribonacci was never able to compute more than the first 3 terms of his sequence. Even more sadly, one cold night he performed an extraordinary mental effort that dilated one of the blood vessels in his brain, causing severe hemorrhage and killing him instantly. This is clinically known as an aneurysm, but of course Tribonacci did not know this (it is suspected that even pronouncing the word aneurysm would have been an impossible task for him).
Write a program that changes history and finds the nth term in the Tribonacci sequence modulo 1,000,000,009.
Input
The input contains several test cases (at most 400).
Each test case contains a single integer n (1 ≤ n ≤ 1016), the desired term in the Tribonacci sequence.
The last line of the input contains a single 0 and should not be processed.
Output
For each test case, output the nth term in the Tribonacci sequence on a single line. This number might be huge, so output the number modulo 1,000,000,009.
Sample input and output
|
standard input
|
standard output
|
|
1
2 3 4 5 6 7 8 9 10 100 10000 10000000 100000000000 10000000000000000 0 |
0
1 2 3 6 11 20 37 68 125 616688122 335363379 272924536 48407255 163452242 |