Задача A. Автомобильные номера ≡

Условие

При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия.

Получение свидетельских показаний — непростая работа. Ситуация осложняется тем, что очень часто свидетели могут только приблизительно вспомнить номер автомобиля. При этом с большой вероятностью опрашиваемый может перепутать порядок цифр или букв в номере.

По полученному от свидетеля происшествия номеру, подсчитайте, сколько различных номеров может получиться из него перестановкой букв и/или цифр, а также выведите все такие номера.

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла

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

Формат выходного файла

Примеры тестов

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача B. Беговые дорожки 2 ≡

Условие

Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

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

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.

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

Формат входного файла

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

Формат выходного файла

Первая строка выходного файла должна содержать число забегов r в предлагаемой схеме. Следующие r строк должны состоять из n − 1 числа — номеров спортсменов, выставляемых на дорожки в каждом из забегов.

Ограничения

2 ≤ n ≤ 100.

1 ≤ r ≤ 1000.

Примеры тестов

4 1
2 3

4
4 2 1
1 3 4
2 1 3
3 4 2

Задача C. Код Грея ≡

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

• первая строка последовательности — входная строка;
• каждая строка входит в последовательность один раз;
• соседние строки последовательности отличаются друг от друга ровно в одном символе.

Формат входного файла

Во входном файле содержится строка из символов 0 и 1

Формат выходного файла

Выходной файл должен содержать 2^N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

Примеры тестов

1

1
0

110

110
111
101
100
000
001
011
010

Задача D. k-почтимонотонность ≡

Условие

Рассмотрим последовательность a₁, …, a_n. Назовём её k-почтимонотонной, если среди неравенств a₁ ≤ a₂, a₂ ≤ a₃, …, a_n − 1 ≤ a_n ровно k неверных.

Даны числа 0 ≤ b₁, b₂, …, b_m ≤ n, где b₁ + b₂ + …  + b_m = n. Найдите количество k-почтимонотонных последовательностей, в которой число 1 встречается b₁ раз, 2 встречается b₂ раз, …, m — b_m раз.

Ответ требуется вывести по модулю 10⁹ + 9.

Формат входного файла

В первой строке заданы два натуральных числа k и m. В следующей строке задано m натуральных чисел b_i.

Формат выходного файла

Выведите единственное число — ответ на поставленную задачу.

Ограничения

1 ≤ k ≤ 100;

1 ≤ m ≤ 26;

1 ≤ b_i ≤ 100;

Примеры тестов

2 2
2 2

1