Матрица \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}-битоый целочисленный тип.