Liczby Leonarda

Limit pamięci: 32 MB

Znane wszystkim liczby Fibonacciego to nie jedyny dorobek Leonarda z Pizy, zwanego też Fibonaccim. Niech oraz dla . Ciąg nazywamy liczbami Leonarda. Twoim dzisiejszym zadaniem, w 800 lat po Leonardzie Fibonaccim, jest policzenie sumy

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby całkowite i ,
• obliczy żądaną sumę,
• zapisze ostatnie dziewięć cyfr wyniku na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera dwie liczby całkowite dodatnie i (, mieści się w 64-bitowym typie całkowitym bez znaku).

Wyjście

Jedyny wiersz wyjścia powinien zawierać dokładnie dziewięć ostatnich cyfr dziesiętnych szukanej liczby.

Przykład

Dla danych wejściowych:

3 2

poprawną odpowiedzią jest:

000000036

W tym przykładzie szukana suma to .

Autor zadania: Tomasz Kulczyński.