문제

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