# Leonardo's Numbers

### Memory limit: 32 MB

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.*