Задачі
Степень Паскаля
Степень Паскаля
Матрица \textit{Паскаля} - это (бесконечная) матрица, которая определяется следующим образом (строки и колонки нумеруются с нуля):
\textbf{Pascal\[row, column\]} = \textbf{Comb(row, column) for 0 }≤ \textbf{column }≤ \textbf{row}
и ноль иначе, где \textbf{Comb(n, k)} - количество комбинаций из \textbf{n} объектов по \textbf{k }(биномиальный коэффициент).
Напишите программу, которая вычислит элементы матрицы степеней Паскаля:
\textbf{Pascal^P} = \textbf{Pascal × Pascal × ... × Pascal} (\textbf{P} множителей)
Так как матрица нижняя треугольная, все степени являются нижними треугольными, и только верхний левый угол \textbf{n} на \textbf{n} используется при вычислении коэффициентов в верхнем левом углу \textbf{n} на \textbf{n} степени.
\InputFile
Первая строка содержит количество тестов \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{1000}).
Каждый тест состоит из одной строки, содержащей четыре целых числа. Первое число - номер теста. Второе число - степень \textbf{p} (\textbf{1 }≤ \textbf{p }≤ \textbf{100000}), в которую следует возвести Паскалевскую матрицу. Третье и четвертое число задают строку \textbf{r }и колонку \textbf{c }(\textbf{0} ≤ \textbf{c} ≤ \textbf{r} ≤\textbf{100000}) искомого элемента.
\OutputFile
Для каждого теста вывести в одной строке его номер и требуемый элемент степени Паскалевской матрицы. Входные данные таковы, что результат помещается в \textbf{64}-битоый целочисленный тип.
Вхідні дані #1
3 1 1 8 3 2 9 21 13 3 200 100000 99998
Вихідні дані #1
1 56 2 8759577256290 3 199998000000000