n комнат с номерами от 0 до n - 1. Комната 0 уже построена. Для каждой другой комнаты i план задаёт parent[i] — комнату, к которой i пристраивается вплотную; строить i можно только когда parent[i] уже готова. Для комнаты 0 parent[0] = -1.
Строится по одной комнате за раз, и в каждый момент можно выбрать любую комнату, чья «родительская» уже построена. План устроен так, что в итоге все комнаты связаны с комнатой 0.
Посчитайте, сколькими разными порядками можно построить все комнаты. Ответ может быть большим, поэтому верните его по модулю 10⁹ + 7.parent=[-1, 0, 0] → 2
Комнаты 1 и 2 обе пристраиваются к 0, поэтому их можно строить в любом порядке: 1 → 2 или 2 → 1.
parent=[-1, 0, 0, 1] → 3
Подходят 1 → 2 → 3, 1 → 3 → 2 и 2 → 1 → 3: комната 3 всегда идёт после 1.
parent=[-1, 0, 1, 2] → 1
Комнаты вытянуты цепочкой, порядок ровно один.
parent=[-1, 0, 0]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 91 тест на сервере, включая скрытые.