Степень Паскаля
Матрица Паскаля - это (бесконечная) матрица, которая определяется следующим образом (строки и колонки нумеруются с нуля):
Pascal[row, column] = Comb(row, column) for 0 ≤ column ≤ row
и ноль иначе, где Comb(n, k) - количество комбинаций из n объектов по k (биномиальный коэффициент).
Напишите программу, которая вычислит элементы матрицы степеней Паскаля:
Pascal^P = Pascal × Pascal × ... × Pascal (P множителей)
Так как матрица нижняя треугольная, все степени являются нижними треугольными, и только верхний левый угол n на n используется при вычислении коэффициентов в верхнем левом углу n на n степени.
Входные данные
Первая строка содержит количество тестов k (1 ≤ k ≤ 1000).
Каждый тест состоит из одной строки, содержащей четыре целых числа. Первое число - номер теста. Второе число - степень p (1 ≤ p ≤ 100000), в которую следует возвести Паскалевскую матрицу. Третье и четвертое число задают строку r и колонку c (0 ≤ c ≤ r ≤100000) искомого элемента.
Выходные данные
Для каждого теста вывести в одной строке его номер и требуемый элемент степени Паскалевской матрицы. Входные данные таковы, что результат помещается в 64-битоый целочисленный тип.