Покращення доріг
У країні є міст і двохстороння дорога, причому з кожного міста можна добратись до будь-якого іншого міста, рухаючись тільки по дорогам. Міста пронумеровані цілими числами від до включно.
Всі дороги спочатку погані, проте керівництво хоче покращити стан деяких доріг. Будемо вважати, що громадяни задоволені покращенням доріг, якщо на шляху від столиці, що розміщена в місті , до будь-якого міста не більше однієї поганої дороги на шляху.
Визначіть кількість способів покращення якості деяких доріг так, щоб задовольнити вимогам громадян. Оскільки відповідт будет більшим, виведіть його за модулем .
Вхідні дані
В першому рядку задано одне ціле число — кількість міст в країну. В наступному рядку задано цілих додатніх чисел — опис доріг країни. Число означає, що в країні є дорога, що з'єднує місто і місто .
Вихідні дані
Виведіть кількість способів покращеня якість доріг за модулем .