K-ангуляция
Очень сложная
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 256 мегабайт
(k_1, k_2)-ангуляцией выпуклого N-угольника назовём разбиение его попарно непересакющимися диагоналями (допускается лишь взможность, чтобы две диагонали имели общий конец) на многоугольники, каждый из которых имеет не менее k_1, но не более k_2 вершин.
Требуется вычислить количество различных (k_1, k_2)-ангуляций выпуклого N-угольника. Две (k_1, k_2)-ангуляции считаются различными, если одна из них соержит диагональ, которая не входит во вторую.
Входные данные
В едиственной строке входного файла задаются три натуральных числа N, k_1 и k_2 (3 ≤ N ≤ 500, 3 ≤ k_1 ≤ k_2 ≤ N).
Выходные данные
В выходной файл выведите остаток от деления количества (k_1, k_2)-ангуляций на 10^9+7.
Примеры
Ввод #1
Ответ #1
Отправки 2