n целых чисел, каждое от 1 до m. Пройдём по нему слева направо и будем отмечать **рекорды** — элементы, строго большие всех элементов перед ними. Первый элемент всегда рекорд.
Например, в массиве [2, 1, 3, 3, 5] рекорды — это 2, 3 (первая тройка) и 5, всего три.
Посчитайте, сколько существует массивов длины n со значениями от 1 до m, в которых ровно k рекордов. Ответ может быть большим, верните его по модулю 10⁹ + 7.n=3, m=2, k=2 → 3
Подходят [1, 2, 1], [1, 2, 2] и [1, 1, 2]: в каждом рекорд ставят первый элемент и первая двойка.
n=2, m=4, k=1 → 10
Второй элемент не должен превышать первый: 1 + 2 + 3 + 4 = 10 массивов.
n=4, m=3, k=4 → 0
Четыре рекорда требуют четырёх строго возрастающих значений, а их всего три.
n ≤ 50m ≤ 100k ≤ nn=3, m=2, k=2
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 112 тестов на сервере, включая скрытые.