n башен высотой 1, 2, …, n — все высоты разные, каждая встречается ровно один раз. Наблюдатель смотрит на ряд слева. Башню видно, если левее неё нет ни одной более высокой башни; первая башня видна всегда.
Например, в ряду [2, 1, 4, 3, 5] видны башни высотой 2, 4 и 5.
Посчитайте, сколько существует расстановок, при которых наблюдатель видит ровно visible башен. Ответ может быть большим — верните его по модулю 10⁹ + 7.n=4, visible=3 → 6
Подходят 6 расстановок, например [1, 2, 4, 3]: видны 1, 2 и 4, а 3 закрыта башней 4.
n=3, visible=1 → 2
Видна только одна башня, значит, первой стоит самая высокая: [3, 1, 2] и [3, 2, 1].
n=6, visible=6 → 1
Все башни видны только при расстановке по возрастанию.
n ≤ 1000visible ≤ nn=4, visible=3
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 60 тестов на сервере, включая скрытые.