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

Задача A. Волшебство на матрицах

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

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

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

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

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

Каждая из следующих строк описывает очередной запрос и содержит три целых положительных числа — номер строки $i$, номер столбца $j$ и количество предварительных применений заклинания $k(1 \leq i, j, k \leq 10^5)$ соответственно.

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

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

Примеры

Вход

2
2 3 1
1 1 3

Выход

6
1

Вход

3
4 5 7
3 3 3
2 1 10

Выход

39600
100
11