8506번 - Leonardo's Numbers 다국어

The famous Fibonacci numbers are not the only discovery of Leonardo of Pisa, also known as Fibonacci. Let us denote L₀ = L₁ = 1 and L_i+1 = L_i + L_i-1 + 1  for i ≥ 1. The sequence (L_i) 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: L₀^k + L₁^k + L₂^k + … + Ln^k.

Task

Write a program which:

• reads from the standard input the integers n and k,
• evaluates the expression,
• writes the last 9 digits of the result to the standard output.

The first and only line of input contains two positive integers n and k (k ≤ 13, n 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.