Областная олимпиада по информатике 2019 год, 9 класс
Задача A. Волшебство на последовательностях
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую последовательность ее префиксной суммой!
Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл последовательность очень большого размера, каждый элемент которой равен 1, и очень много раз применил к ней вышеописанное заклинание.
В этой задаче, вам предстоит показать, что ваши навыки программирования ничем не уступают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в i-м ряду после k применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от деления этих чисел на 1000000007.
Формат входного файла
Первая строка ввода содержит целое число Q — количество запросов к вашей программе.
Каждая из следующих Q строк описывает очередной запрос и содержит два целых положительных числа — номер столбца и количество предварительных применений заклинания соответственно.
Формат выходного файла
Выведите $Q целых чисел, по одному в строке — значение в ячейке в i-м ряду после k$ применений заклинания по модулю 1000000007.
Система оценки
Подзадача 1 (10 баллов) — 1 <= Q <= 10^5, 1 <= i, k <= 5
Подзадача 2 (10 баллов) — 1 <= Q <= 10^5, 1 <= i <= 10^5, k=1
Подзадача 3 (20 баллов) — 1 <= Q <= 10^5, 1 <= i,k <= 100
Подзадача 4 (20 баллов) — 1 <= Q <= 10^5, 1 <= i,k <= 10^3
Подзадача 5 (40 баллов) — 1 <= Q <= 10^5, 1 <= i,k <= 10^5
Пример:
Вход 2 2 1 1 3Ответ
2 1
Замечание
Напомним, что последовательность - это одномерный массив содержащий целочисленные значения. Один из возможных примеров последовательности размерностью 4 приведен ниже:
1 | 2 | 3 | 4 |
Префиксной суммой называется последовательность, где каждый элемент заменен на сумму чисел в соответствующем ему подпоследовательности, с противоположной вершиной в ячейке (1, 1). Формально, определим префиксную сумму последовательности A как последовательность B такую, что для любых i > 0 выполняется B_i = A_i + B_{i - 1}
В то время как значения в ячейках B с i = 0 равны нулю.
Например префиксной суммой данной последовательности
1 | 2 | 0 | 1 |
Будет следующая последовательность:
1 | 3 | 3 | 4 |
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.