03. Цветы#

📝 Условие#

Сурок ест красные цветы по одному, а белые — только группами ровно по k. Для каждого запроса [a, b] посчитайте количество способов съесть от a до b цветов (по модулю 10⁹+7).

📥 Входные данные#

В первой строке два числа t и k (1 ≤ t, k ≤ 10⁵). Далее t строк a b (1 ≤ a ≤ b ≤ 10⁵).

📤 Выходные данные#

t строк — количество способов по модулю 10⁹ + 7.

🧪 Тесты#

Тест 1#

Ввод:

3 2
1 3
2 3
4 4

Вывод:

6
5
5

Тест 2#

Ввод:

2 1
1 1
1 3

Вывод:

2
14

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня