Ступінь Паскаля
Матриця Паскаля — це (нескінченна) матриця, визначена наступним чином (рядки та стовпці нумеруються з нуля):
Pascal[рядок, стовпець] = Comb(рядок, стовпець) для 0 ≤ стовпець ≤ рядок
і нуль в інших випадках, де 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-бітовий цілочисловий тип.