문제

백준 11444 피보나치 수 6

위 문제를 푼 후에 이 문제를 푸는 것을 추천합니다.

피보나치 함수 $f$는 아래와 같이 정의된다.

$f(0)=0,\quad f(1)=1$

$f(x)=f(x-1)+f(x-2)\ \quad (x\ge2)$

그리고 아래와 같은 함수 $F$를 새로 정의하자.

$F(0) = 1$

$F(x) = f(x) + f(x-1) + C \sum_{i=0}^{x-1}f(i)\ \quad (x\ge1)$

이때, $F(1) + F(3) + \cdots + F(2K-1)$ 의 값을 $1\,000\,000\,007$ 로 나눈 나머지를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 $C(1 \le C < 1\,000\,000\,007)$와 $K(1 \le K \le \textbf{1 000 000 000 000 000 000}\ (=10^{18}))$가 공백으로 구분되어 주어진다.

출력

$F(1) + F(3) + \cdots + F(2K-1)$ 의 값을 $1\,000\,000\,007$ 로 나눈 나머지를 출력한다.

부분점수

예제 입력 1

2 2

예제 출력 1

8

힌트

• 입력으로 들어오는 $K$의 값이 4바이트 정수 자료형(int)의 최댓값보다 크므로, 8바이트 정수 자료형(C/C++: long long int, Java: long)을 사용해야 함에 유의하자.