문제

백준 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)을 사용해야 함에 유의하자.