시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB102483745.679%

문제

A young boy got really curious about binary strings. This string contains only 1s and 0s hence the name binary. His particular interest was about those strings for which no two ones are side by side. Specifically he wanted to know the number of strings of a certain length that consisted of only ones and zeroes and there are no two consecutive ones.

After solving this problem, the young boy got even more curious. Now he wants to know the number of binary strings which satisfies the following properties:

  • The length of the string is between L and R, inclusive (1 ≤ L ≤ R ≤ 1018)
  • The length of string is divisible by an integer K. (3 ≤ K ≤ 109)
  • It is a binary string with no two consecutive ones.

Now can you help him to find out the number of strings that satisfies the above conditions? Since the number can be huge, you need to print it modulo 1 000 000 007.

입력

The first line is an integer T (1 ≤ T ≤ 10 000), the number of tests. In the next T lines there are three integers L, R and K.

출력

Print T lines, in each line print the case id and the result modulo 1 000 000 007. See the samples for more details.

예제 입력 1

2
1 10 3
1 10 5

예제 출력 1

Case 1: 115
Case 2: 157

힌트

For the first case some example strings are “101”, “000”, “010” “101001”, “000010000” etc.