На окружности отметили N точек и пронумеровали их последовательно числами от 1 до N. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами i и j.
Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).
Входные данные
Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N).
Выходные данные
Требуется вывести остаток от деления количества ломаных на 10
9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1 3
|
5
|
|
2
|
5 1 4
|
12
|