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:
.
Task
Write a program which:
reads from the standard input the integers and ,
evaluates the expression,
writes the last 9 digits of the result to the standard output.
Input
The first and only line of input contains two positive integers and
(, fits in a 64-bit unsigned integer type).
Output
The only line of output should contain the last 9 digits of the decimal representation of the
result of the expression.
Example
For the input data:
3 2
the correct result is:
000000036
The expression corresponding to this example is .
Task author: Tomasz Kulczynski.
Kontakt
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.