Задача #2597

(Л. Шастин) По каналу связи передаются сообщения, содержащие только семь букв: А, М, Н, Е, З, И, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А - 010, М - 000, Н - 100, Е - 101, З - 001, И - 011, Я - 1101. Как можно сократить код для буквы Я таким образом, чтобы суммарная длина всех кодовых слов осталась прежней, а также сохранилось выполнение условия Фано? При этом допускается изменять коды, соответствующие остальным буквам. В качестве ответа укажите количество возможных (более коротких) кодовых слов для буквы Я.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.