Đếm số lượng xâu nhị phân thỏa mãn các điều kiện sau:

• Độ dài của xâu nằm trong khoảng ~[L .. R]~.

• Độ dài của xâu chia hết cho ~K.~

• Xâu không chứa ~2~ ký tự ~1~ liên tiếp nhau.

Input

• Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ test ~(1 \le T \le 10^4)~.

• Trong ~T~ dòng tiếp theo, mỗi dòng ghi ~3~ số nguyên dương ~L, R~ và ~K~ ~(1 \le L \le R \le 10^{18}, 3 \le K \le 10^9)~.

Output

• Với mỗi bộ test, in trên một dòng kết quả sau khi chia dư ~10^9+7~.

Sample Input 1

5
1 10 1
1 10 2
1 10 3
1 10 4
1 10 5

Sample Output 1

374
231
115
63
157