| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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.
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 |
