Nếu đã học qua đại số, ta sẽ không lạ lẫm gì về việc khai triển công thức ~(x + 1)^n~.

• ~(x + 1)^1 = x + 1~

• ~(x + 1)^2 = x^2 + 2x + 1~

• ~(x + 1)^3 = x^3 + 3x^2 + 3x + 1~

• ~(x + 1)^4 = x^4 + 4x^3 + 6x^2 + 4x + 1~

• ~\ldots~

Và hệ số của ~x^k~ trong khai triển ~(x + 1)^n~ đúng bằng ~C_{n}^{k}~.

Ta quy định, ~F(n)~ là tổng số lượng số ~k~ ~(0 \le k \le n)~ có hệ số ~x^k~ cùng đồng dư với ~\phi~ khi ~\mod 2~. Hay nói cách khác: ~F(n) = \sum_{k = 0}^{n} [C_{n}^{k} \equiv \phi \mod 2]~ — với ~\phi~ là một số cho trước.

Có ~q~ truy vấn cần giải quyết. Ở truy vấn thứ ~t~, ta được cho ~2~ số nguyên ~l_t, r_t~ ta cần xác định ~S_t = \left(\sum_{i = l_t}^{r_t} F(i) \right) \bmod (10^9+7)~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~q, \phi~ (~1 \le q \le 10^5, 0 \le \phi \le 1~) – thể hiện số lượng truy vấn và giá trị của ~\phi~.

• ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~l_t, r_t~ (~1 \le l_t \le r_t \le 10^{18}~).

Output

• In ra ~q~ dòng, dòng thứ ~t~ là giá trị ~S_t~ tính được (~1 \le t \le q~).

Scoring

Sample Input 1

2 0
1 4
3 4

Sample Output 1

4
3

Sample Input 2

2 1
1 2
3 4

Sample Output 2

4
6

Notes

Bên dưới là Tam giác Pascal:

Trong ví dụ 1, các cặp ~\{n,k\}~ thoả mãn là:

• Truy vấn 1: ~\{2,1\}~, ~\{4,1\}~, ~\{4,2\}~, ~\{4,3\}~

• Truy vấn 2: ~\{4,1\}~, ~\{4,2\}~, ~\{4,3\}~

Trong ví dụ 2, các cặp ~\{n,k\}~ thoả mãn là:

• Truy vấn 1: ~\{1,0\}~, ~\{1,1\}~, ~\{2,0\}~, ~\{2,2\}~

• Truy vấn 2: ~\{3,0\}~, ~\{3,1\}~, ~\{3,2\}~, ~\{3,3\}~, ~\{4,0\}~, ~\{4,4\}~.