|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||68||21||9||34.615%|
The famous Fibonacci numbers are not the only discovery of Leonardo of Pisa, also known as Fibonacci. Let us denote L0 = L1 = 1 and Li+1 = Li + Li-1 + 1 for i ≥ 1. The sequence (Li) 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: L0k + L1k + L2k + … + Lnk.
Write a program which:
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.