Гондола Мао-Конга - известная достопримечательность Тайбея. Это подвесная дорога в виде окружности, которая имеет одну станцию и n гондол, пронумерованных от 1 до n. Гондолы движутся по этой дороге в одном направлении. Изначально, после гондолы с номером i мимо станции проезжает гондола с номером (i + 1) для i < n. Если i = n, то следующей проезжает гондола с номером 1.

Иногда гондолы могут ломаться. К счастью, у нас есть неограниченное количество запасных гондол, которые имеют номера (n + 1), (n + 2) и так далее. Когда гондола ломается, ее заменяют запасной с наименьшим номером среди тех, которые еще не были использованы. При этом новая гондола устанавливается на то же место, где стояла сломавшаяся. Например, если было пять гондол, и одна из них сломалась, то она будет заменена на гондолу с номером 6.

Вам нравится стоять на станции и смотреть на проезжающие мимо гондолы. Последовательностью гондол называется последовательность из n номеров гондол в порядке, в котором они проезжают мимо станции. Возможно, что одна или несколько гондол сломались до того, как вы пришли на станцию, но пока Вы смотрите на движение гондол ни одна из гондол не ломается.

Обратите внимание, что одному и тому же порядку гондол может соответствовать несколько последовательностей, в зависимости от того, какая из гондол приехала на станцию первой. Например, если ни одна из гондол не ломалась, то возможные последовательности гондол (2, 3, 4, 5, 1) и (4, 5, 1, 2, 3), а (4, 3, 2, 5, 1) - не является последовательностью гондол, потому что гондолы приехали в неправильном порядке.

Если гондола с номером 1 сломается, то Вы сможете увидеть последовательность гондол (4, 5, 6, 2, 3). Если после этого сломается гондола с номером 4, ее заменят на гондолу с номером 7, и Вы сможете увидеть последовательность (6, 2, 3, 7, 5). Если после этого гондола с номером 7 сломается, ее заменят на гондолу с номером 8, и Вы сможете увидеть последовательность (3, 8, 5, 6, 2).

Последовательностью замен называется последовательность номеров сломавшихся гондол в том порядке, в котором они ломались. В предыдущем примере последовательность замен - (1, 4, 7). Будем считать, что последовательность замен r порождает последовательность гондол g, если после того, как гондолы ломались и заменялись в соответствии с последовательностью замен r, Вы можете увидеть последовательность гондол g.

Проверка последовательности гондол

В первых трех подзадачах вам необходимо проверить, является ли последовательность гондол корректной. Вам необходимо реализовать функцию valid(n, inputSeq), где

• n - длина последовательности;
• inputSeq - массив длины n, inputSeqi - элемент последовательности на месте i для 0 ≤ i ≤ n - 1;
• функция должна возвращать 1, если переданная последовательность является последовательностью гондол, и 0 в противном случае.

Подзадачи 1, 2, 3

Примеры

В таблице ниже приведены примеры последовательностей, которые являются и не являются последовательностями гондол.

Последовательность замен

В следующих трех подзадачах Вы должны построить последовательность замен, которая порождает заданную последовательность гондол. Вы можете построить любую из таких последовательностей.

Вам необходимо реализовать функцию replacement(n, gondolaSeq, replacementSeq), где

• n - длина последовательности;
• gondolaSeq - массив длины n. Гарантируется, что gondolaSeq является последовательностью гондол, gondolaSeqi - это i-ый элемент последовательности, для 0 ≤ i ≤ n - 1;
• функция должна возвращать l - длину последовательности замен;
• replacementSeq - массив, достаточно большой, чтобы вместить последовательность замен; Вы должны вернуть последовательность замен, записав ее i-ый элемент в replacementSeqi для всех 0 ≤ i ≤ l - 1.

Подзадача 4, 5, 6

Примеры

Подсчет последовательностей замен

В следующих четырех подзадачах вы должны определить количество последовательностей замен, которые порождают заданную последовательность (которая может быть последовательностью гондол, а может не быть) по модулю 109 + 9. Вы должны реализовать функцию countReplacement(n, inputSeq).

• n - длина переданной последовательности;
• inputSeq - массив длины n, inputSeqi - это i-ый элемент переданной последовательности, для всех 0 ≤ i ≤ n - 1.
• если переданная последовательность является последовательностью гондол, Вы должны определить количество последовательностей замен, которые порождают данную последовательность гондол, и вернуть остаток от деления этого количества на 109 + 9. Если переданная последовательность не является последовательностью гондол, функция должна возвращать 0. Если переданная последовательность является последовательностью гондол, но ни одна гондола не сломалась, функция должна вернуть 1.

Подзадачи 7, 8, 9, 10

Примеры

Входные данные

Первая строка содержит номер подзадачи t, которую должна решать ваша программа (1 ≤ t ≤ 10);

Вторая строка содержит длину n переданной последовательности;

Если t равно 4, 5 или 6, то третья строка содержит gondolaSeq0, ..., gondolaSeqn-1. Иначе она содержит inputSeq0, ..., inputSeqn-1.

Выходные данные

Для каждого вопроса будет выведен соответствующий ответ.