G. Пещеры Эль-Толль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Досторические пещеры Эль Толль расположены в Мойя (Барселона). Вы узнали, что в одном из n тайников в пещерах спрятано сокровище. Можно считать, что вероятность найти сокровище в каждом из тайников равна 1 / n.

Вы не можете попасть в пещеру сами, но вы построили робота, который может искать сокровище в пещерах. Каждый день вы можете послать робота обыскать ровно k различных тайников. Если ни в одном из них нет сокровища, то, очевидно, робот вернется ни с чем. В пещерах очень темно, поэтому робот может не найти сокровище, даже если будет обыскивать правильный тайник. Формально, если один из обыскиваемых тайников содержит сокровище, робот найдет его с вероятностью 1 / 2, иначе он вернется ни с чем. Каждый раз, когда робот обыскивает тайник с сокровищем, вероятность его успеха не зависит от всех предыдущих попыток (то есть, вероятность не найти сокровище за x попыток обыскать правильный тайник равна 1 / 2x).

Каково среднее количество дней, которое понадобится для того, чтобы найти сокровище при оптимальном выборе порядка обыска тайников? Выведите ответ в виде рационального числа по модулю 109 + 7. Формально, пусть ответ имеет вид несократимой дроби P / Q, тогда вам требуется вывести число . Гарантируется, что Q не делится на 109 + 7.

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

В первой строке записано число тестов T (1 ≤ T ≤ 1000).

Каждая из следующих T строк содержит два целых числа n и k (1 ≤ k ≤ n ≤ 5·108) для очередного теста.

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

Для каждого теста выведите ответ на отдельной строке.

Пример
Входные данные
3
1 1
2 1
3 2
Выходные данные
2
500000007
777777786
Примечание

В первом примере робот будет последовательно обыскивать единственный тайник. Среднее число попыток в этом случае равно 2. Обратите внимание, что несмотря на то, что мы точно знаем, где находится сокровище, роботу все равно придется возвращаться в тайник, пока он успешно не найдет там сокровище.

Во втором примере ответ равен 7 / 2, если робот будет обыскивать тайники по очереди. В третьем тесте ответ равен 25 / 9.