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