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