시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

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.

예제 입력

3 2

예제 출력

000000036

힌트