Guest
Моя анкета на профи ру Ассоциация репетиторов Мой вк Группа вк Сайт олимпиады Задача 6. Робот-строитель Имя входного файла: Имя выходного файла: Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Ваня купил робота-строителя. Вместе с роботом в комплекте идут кубики. Из этих кубиков робот может собирать и разбирать некоторые конструкции. Чтобы робот заработал, все кубики надо выложить перед ним в один ряд. После этого можно дать роботу команду постройки некоторой конструкции. Налюбовавшись тем, что построил робот, ему можно скомандовать, чтобы он её разобрал. Тогда робот вернет все использованные кубики обратно в ряд. После нескольких запусков робота Ваня заметил, что некоторые кубики возвращаются не на свои места. Причем после любой конструкции кубики переставляются одинаково. Ваня захотел покрасить кубики, для этого у него есть краски различных цветов. Ваня не хочет трогать кубики после покраски и разложения их перед роботом, но пользоваться роботом он хочет. Также Ваня очень любит симметрию, поэтому он хочет, чтобы перед началом постройки конструкции ряд из кубиков всегда был симметричным. Ряд из покрашенных кубиков называется симметричным, если первый кубик слева имеет тот же цвет, что и первый кубик справа, аналогично для второго, третьего и так далее. В связи с этим у Вани возник вопрос, а сколько существует вариантов раскрасить ряд из кубиков перед роботом, чтобы после любого количества построек ряд был симметричным. Помогите Ване узнать ответ на этот вопрос. Формат входных данных В первой строке входного файла записаны два целых числа 𝑁 и 𝑀 — количество кубиков и количество различных цветов для покраски кубиков соответственно (1 ⩽ 𝑁, 𝑀 ⩽ 2 · 105 ). Во второй строке заданы 𝑁 целых чисел, задающие перестановку кубиков после постройки. Число на месте 𝑖 означает, что после выполнения постройки робот переместит кубик, лежащий на 𝑖-м месте слева на 𝑝𝑖-е место (1 ⩽ 𝑝𝑖 ⩽ 𝑁). Гарантируется, что после выполнения постройки кубики перемещаются на различные места. Формат выходных данных В выходной файл необходимо вывести единственное число — количество различных вариантов покраски ряда из кубиков, таких чтобы после любого количества построек ряд из кубиков был бы симметричным. Поскольку ответ может быть достаточно большим, выведите остаток от деления его на число 109 7. Два способа покраски считаются различными, если существует кубик в ряду, полученном первым способом, такой что соответствующий кубик в ряду, полученном вторым способом, имеет цвет отличный от цвета кубика в первом ряду. Примеры 2 2 1 2 2 3 2 3 2 1 4
