Ступінь Паскаля#6394
Матриця Паскаля — це (нескінченна) матриця, визначена наступним чином (рядки та стовпці нумеруються з нуля):
і нуль в інших випадках, де Comb(n, k) — це кількість комбінацій з об'єктів по (біноміальний коефіцієнт).
Напишіть програму, яка обчислює елементи матриці степенів Паскаля:
( множників)
Оскільки матриця є нижньою трикутною, всі її степені також є нижніми трикутними, і лише верхній лівий кут розміром на використовується для обчислення коефіцієнтів у верхньому лівому куті на степені.
Перший рядок містить кількість тестів (1 \le k \le 1000).
Кожен тест складається з одного рядка, що містить чотири цілі числа. Перше число — номер тесту. Друге число — степінь (1 \le p \le 100000), до якої потрібно піднести матрицю Паскаля. Третє і четверте числа задають рядок і стовпець (0 \le c \le r \le 100000) шуканого елемента.
Для кожного тесту виведіть в одному рядку його номер і потрібний елемент степеня матриці Паскаля. Вхідні дані такі, що результат вміщується в -бітовий цілочисельний тип.
Приклад 1