In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.