Страница: 1 Отображать по:
#610
Ломаные
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На окружности отметили \(N\) точек и пронумеровали их последовательно числами от 1 до \(N\). Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами \(i\) и \(j\).

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Входные данные

Вводятся три натуральных числа \(N\), \(i\), \(j\) (2 ≤ \(N\) ≤ 2 000, 1 ≤ \(i\) < \(j\) ≤ \(N\)).

Выходные данные

Требуется вывести остаток от деления количества ломаных на \(10^9\).

Примеры
Входные данные
4 1 3
Выходные данные
5
Входные данные
5 1 4
Выходные данные
12
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест