Программист приобрел новый гаджет. Алфавитная клавиатура гаджета представляет собой матрицу размером 4х8:
После падения гаджета на пол клавиатура стала работать лишь частично. Теперь после включения гаджета первым нажатием можно выбрать любую букву, а каждым следующим нажатием выбираются лишь те буквы, которые расположены от предыдущей нажатой клавиши на «ход коня» (две клавиши в одну сторону и одна в перпендикулярную).
Например, если первой была нажата клавиша «Ф», то следующей может быть нажата только одна из клавиш «К», «Г», «Е», «О», «Ю», «Ъ», а если первой была нажата «А», то следующими могут быть либо «К», либо «С».
Программист стал набирать на клавиатуре слова. Словами он считает последовательности букв, в которых гласные и согласные буквы чередуются (для лучшей читабельности). Его заинтересовало, сколько таких слов длиной в N букв, начиная с заданной буквы, можно набрать на клавиатуре гаджета.
Количество слов длиной в 9 букв, которые можно набрать, начиная с буквы «Щ», равно …