Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BANGKOK2016G - Binary Strings

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 ≤ 10^18) 
  • The length of string is divisible by an integer K. (3 ≤ K ≤ 10^9) 
  • 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 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. 

 

Input

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.

Output

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

Example

Input:

2

1 10 3

1 10 5 

 

Output:

Case 1: 115

Case 2: 157 


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


Được gửi lên bởi:adm
Ngày:2017-01-26
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-02-02 13:11:33
đề chưa chính xác lắm , có test case K<3 ,mọi người cẩn thận .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.