Областная олимпиада по информатике 2019 года за 9 класс | Казахстанские олимпиады

Задача A. Волшебство на последовательностях

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую последовательность ее префиксной суммой!

Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл последовательность очень большого размера, каждый элемент которой равен $1$, и очень много раз применил к ней вышеописанное заклинание.

В этой задаче, вам предстоит показать, что ваши навыки программирования ничем не уступают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в $i$-м ряду после $k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от деления этих чисел на $1000000007$.

Формат входного файла

Первая строка ввода содержит целое число $Q$ — количество запросов к вашей программе.

Каждая из следующих строк описывает очередной запрос и содержит два целых положительных числа — номер столбца и количество предварительных применений заклинания соответственно.

Формат выходного файла

Выведите $Q$ целых чисел, по одному в каждой строке - значение ячекйи в $i$-м ряду после $k$ применений заклинания по модулю $1000000007$.

Примеры

Вход

2
2 1
1 3

Выход

2
1