Binary Strings

A string made of only 0s and 1s is called a binary string. A boy became interested in binary strings that never place two 1s side by side. At first he counted how many such strings there are for a fixed length.

After solving that, he added more conditions. He now wants the number of binary strings that satisfy all three of the following.

• The length of the string is between $L$ and $R$, inclusive ($1 \le L \le R \le 10^{18}$).
• The length of the string is a multiple of an integer $K$ ($3 \le K \le 10^9$).
• No two 1s appear consecutively in the string.

The count can be very large, so print it modulo 1,000,000,007.

The first line contains the number of test cases $T$ ($1 \le T \le 10\,000$).

Each of the next $T$ lines contains three integers $L$, $R$ and $K$, separated by spaces.

For each test case, print one line in the form Case x: y. Here $x$ is the test case number starting from 1, and $y$ is the number of binary strings that satisfy the conditions, modulo 1,000,000,007.

For $L = 1$, $R = 10$ and $K = 3$, only the lengths 3, 6 and 9 are counted. Strings that satisfy the conditions include 101, 000, 010, 101001 and 000010000.