Bữa Tiệc Hoa

Một bữa ăn được biểu diễn bằng một dãy các bông hoa, mỗi bông có màu đỏ hoặc màu trắng. Để bữa ăn ngon, có một quy tắc: các bông hoa trắng chỉ được phép xuất hiện thành từng đoạn liên tiếp có độ dài đúng bằng $k$.

Nói cách khác, trong dãy hoa, mọi đoạn cực đại gồm toàn các bông hoa trắng liên tiếp đều phải có độ dài là bội của $k$.

Với mỗi truy vấn gồm hai số $a$ và $b$, hãy đếm tổng số dãy hoa hợp lệ có độ dài nằm trong khoảng từ $a$ đến $b$ (tính cả hai đầu mút). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $t$ và $k$ — số truy vấn và độ dài đoạn hoa trắng bắt buộc.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ mô tả truy vấn thứ $i$.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là số dãy hoa hợp lệ có độ dài từ $a_i$ đến $b_i$, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le t,k\le {10}^5$
• $1\le a_i\le b_i\le {10}^5$

Ví dụ