Трикутник Шибеника#3552

Трикутник Шибеника

1 секунда

64 мегабайти

Середня

Визначення трикутника Шибеника нагадує трикутник Паскаля. Рядки нумеруються зверху, починаючи з $0$ . Кожен рядок $n$ містить $n + 1$ n+1 чисел, індексованих від $0$ до $n$ . Позначимо елемент з індексом $m$ у рядку з індексом $n$ як $R (n, m)$ R(n,m):

R (n, m) = 0 для n < 0 АБО m < 0 АБО m > n

R(n,m) = 0 \text{ для } n < 0 \text{ АБО } m < 0 \text{ АБО } m > n

Перші та останні числа в кожному рядку (які однакові у верхньому рядку) дорівнюють $1$ :

R (n, 0) = R (n, n) = 1

R(n,0) = R(n,n) = 1

Внутрішні значення визначаються за формулою $(U p L e f tE n t r y \cdot U pR i g h tE n t r y + 1) / U pE n t r y$ (UpLeftEntry \cdot UpRightEntry+1)/UpEntry (див. паралелограм у масиві нижче):

R (n + 1, m + 1) = (R (n, m) \cdot R (n, m + 1) + 1) / R (n - 1, m)

R(n+1, m+1) = (R(n,m) \cdot R(n,m+1) + 1)/R(n-1,m)

Напишіть програму, яка обчислює елемент $R (n, m)$ R(n,m) у рядку трикутника Шибеника.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $P$ ( $1 \leq P \leq 1000$ 1 \le P \le 1000), яке вказує на кількість наборів даних, що слідують. Кожен набір даних представлений одним рядком вхідних даних, що складається з $3$ десяткових цілих чисел, розділених пробілами. Перше число — номер набору даних $N$ . Друге число — номер рядка $n$ , а третє число — індекс $m$ у рядку, для якого потрібно знайти $R (n, m)$ R(n,m) — елемент трикутника Шибеника ( $0 \leq m \leq n \leq 50000$ 0 \le m \le n \le 50000).

Вихідні дані

Для кожного набору даних виведіть один рядок вихідних даних. Він повинен містити номер набору даних $N$ , за яким слідує один пробіл, а потім елемент трикутника Шибеника $R (n, m)$ R(n,m), округлений до цілого значення.

Приклади

Приклад 1