Mike and Bob were playing with binary numbers. Mike was quite confident with his problem-solving skills, so he asks Bob to give him a challenge.

Bob gave him some Queries Q. For each query, Mike's task is to count the total numbers distinct of sequences that contain 0's and 1's of each length in the range [L, R] inclusive.

To make these tasks more challenging, Bob wanted that 0's must be present in a group of lengths divisible by K.

Mike needs your help to accomplish this challenge.

Note

Two Sequences \(A\) and \(B\) are Distinct, if their lengths are not same or there exists an index \(i\), for which \(A[i] \neq B[i]\).
The count of sequences can be huge. So, Output the count mod \(10^9 + 7\).

Task

Find all the total numbers of unique sequences which follow the above conditions for each query.

Example

Assumptions

Q = 2, K = 3
L = 2, R = 4
L = 1, R = 5

Approach

Here, Q = 2 and K = 3

Possible sequence with length 1 are (1).
Possible sequence with length 2 is (11).
Possible sequences with length 3 are (000, 111). Note that 0's should appear in a group with a length divisible by K = 3.
Possible sequences with length 4 are (0001, 1000, 1111).
Possible sequence with length 5 are (00011, 11000, 10001, 11111).
For Query 1
- Mike can form 6 different sequences of length [2, 4] with groups of lengths divisible by 3.
For Query 2
- Mike can form 11 different sequences of length [1, 5] with groups of lengths divisible by 3.

Function Description

Complete the max_count function provided in the editor. This function takes the following 3 parameters and returns the answer integer.

K: Represents the length of a group of 0's.
L: Represents the starting range of length of sequences.
R: Represents the ending range of length of sequences.

Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains two integers Q and K denoting the number of Queries and length of group of 0's.
Q lines follow:
- For each Query, a single line contains two integers L and R denoting the range of length of sequences.

Output Format

For each query(in a separate line), print the total numbers of unique/distinct sequences with length in range [L, R] and \(0's\) must be present in a group of lengths divisible by K. Don't forget to take modulo 1000000007(10⁹+7)

Constraints

\(1 \le Q \le 5 \times 10^5 \\ 1 \le K \le 2 \times 10^5 \\ 1 \le L \le R \le 5 \times 10^5\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.