The famous Fibonacci numbers are not the only discovery of Leonardo of Pisa, also known as Fibonacci. Let us denote and for . The sequence is also called Leonardo's numbers. Today, 800 years after Leonardo Fibonacci's death, we would like to find the value of the following expression: .
Write a program which:
The first and only line of input contains two positive integers and (, fits in a 64-bit unsigned integer type).
The only line of output should contain the last 9 digits of the decimal representation of the result of the expression.
For the input data:
the correct result is:
The expression corresponding to this example is .
Task author: Tomasz Kulczynski.