레오나르도 수

유명한 피보나치 수는 피보나치라고도 불리는 피사의 레오나르도가 남긴 유일한 발견이 아니다. $L_0 = L_1 = 1$이고 $i \ge 1$에 대해 $L_{i+1} = L_i + L_{i-1} + 1$로 정의하자. 이 수열 $(L_i)$을 레오나르도 수라고 부른다.

두 정수 $n$과 $k$가 주어질 때, 다음 식의 값을 구하라.

$L_0^k + L_1^k + L_2^k + \cdots + L_n^k$

이 값은 매우 커질 수 있으므로, 십진법으로 나타냈을 때의 마지막 $9$자리만 출력한다.

표준 입력에서 $n$과 $k$를 읽어 위 합을 계산하고, 결과의 마지막 $9$자리를 표준 출력에 출력하는 프로그램을 작성하라.

한 줄에 두 양의 정수 $n$과 $k$가 공백으로 구분되어 주어진다.

• $1 \le k \le 13$
• $1 \le n \le 2^{64} - 1$ ($n$은 64비트 부호 없는 정수 범위에 들어간다)

$L_0^k + L_1^k + \cdots + L_n^k$의 마지막 $9$자리, 즉 이 값을 $10^9$으로 나눈 나머지를 출력한다. 값이 $9$자리보다 짧으면 앞을 $0$으로 채워 항상 정확히 $9$자리를 출력한다.