이진 문자열

0과 1로만 이루어진 문자열을 이진 문자열이라고 한다. 어떤 아이가 1이 두 번 연속으로 붙어 있지 않은 이진 문자열에 관심을 갖게 되었다. 처음에는 길이가 정해졌을 때 그런 문자열이 몇 개인지 세어 보았다.

이 문제를 풀고 나서 아이는 조건을 더 붙였다. 이제 다음 세 조건을 모두 만족하는 이진 문자열의 개수를 구하려고 한다.

• 문자열의 길이가 $L$ 이상 $R$ 이하이다. ($1 \le L \le R \le 10^{18}$)
• 문자열의 길이가 정수 $K$의 배수이다. ($3 \le K \le 10^9$)
• 문자열 안에 1이 두 번 연속으로 나오지 않는다.

개수가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10\,000$)

다음 $T$개 줄에 각각 정수 $L$, $R$, $K$가 공백으로 구분되어 주어진다.

테스트 케이스마다 한 줄씩 Case x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조건을 만족하는 이진 문자열의 개수를 1,000,000,007로 나눈 나머지이다.

$L = 1$, $R = 10$, $K = 3$이면 길이가 3, 6, 9인 문자열만 센다. 조건을 만족하는 문자열로는 101, 000, 010, 101001, 000010000 등이 있다.