images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
20/09/2024 12:33:32

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2214. Определитель

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Тим разрабатывает модули для QA-системы iNdium-Beta, позволяющей выполнять различные математические расчеты. Тим хочет проверить работу модуля, вычисляющего с помощью распараллеливания определитель матрицы. Для тестирования он решил использовать матрицу `A`, элементы которой вычисляются следующим образом.
`A_{i,j}=B_{i+j-1}`
где `B_k` – первое число в `k`-й строке числового треугольника, построенного следующим образом. `k`-я строка треугольника содержит `k` чисел. Первая строка содержит число 1. Следующая строка треугольника начинается с последнего числа в предыдущей строке, а следующие числа в строке получаются как сумма предыдущего числа в строке и числа над ним.
 1
 1   2
 2   3   5
 5   7  10 15
15  20  27 37 52
52  67  87 ...
...
Например, матрица `3\ times\ 3` будет выглядеть так:
  1  1   2
  1  2   5
  2  5 15
Чтобы убедиться, что его модуль работает правильно, Тиму нужно знать значение определителя для матрицы `A` заданного размера.
Формат ввода
Первая строка ввода одно целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – размер матрицы `A`.
Формат вывода
В первой строке вывести одно целое число — определитель матрицы по модулю `10^9+9`.

Пример ввода

3

Пример вывода

2
loading