Таблица a размера n × n задаётся следующим образом:
- В первой строке и в первом столбце таблицы стоят единицы, то есть ai, 1 = a1, i = 1 для всех i = 1, 2, ..., n.
- Каждое из оставшихся чисел в таблице определяется как сумма числа над ним и числа слева от него. Иными словами, остальные элементы таблицы задаются формулой ai, j = ai - 1, j + ai, j - 1.
Эти условия однозначно задают все элементы таблицы.
Вам даётся число n. Требуется определить значение максимального числа в таблице n × n, построенной по вышеприведенным правилам.
Выходные данные
В единственной строке выведите натуральное число m — максимальное число построенной таблицы.
Примечание
Во втором тесте строки таблицы выглядят так:
{1, 1, 1, 1, 1}, {1, 2, 3, 4, 5}, {1, 3, 6, 10, 15}, {1, 4, 10, 20, 35}, {1, 5, 15, 35, 70}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
5
|
70
|