Відомий менеджер аеропорту

Містер B — менеджер в аеропорту. Одного разу після обіду він виглянув з вікна свого офісу і побачив, що кожен літак в аеропорту був або синього, або зеленого кольору. Перед вечерею він знову поглянув на аеропорт і не побачив жодного літака. Він не пам'ятає, в якому порядку літаки злітали, але точно знає, що між його спостереженнями жоден літак не прилетів. Коли один літак рухається до злітної смуги, решта залишаються на своїх місцях і не рухаються. Іншими словами, якщо розглядати порядок зльоту, то спочатку перший літак рухається до злітної смуги, а всі інші залишаються на своїх місцях. Після того, як перший літак злетів, другий літак рухається до злітної смуги, і так далі, поки всі літаки не злетять. Містер B хоче визначити кількість різних можливих кольорових послідовностей, які він міг би спостерігати, якби він знаходився на злітній смузі весь день.

Аеропорт поділений на $9$ квадратних областей ($3$ рядки x $3$ колонки), в кожній з яких може бути припарковано не більше одного літака. Область, що знаходиться в першій колонці і першому рядку, називається "зоною зльоту". Літак може злетіти тільки з "зони зльоту". Крім того, кожен літак (включаючи той, що знаходиться в зоні зльоту) може пересуватися у вільну сусідню область. Дві області вважаються сусідніми, якщо у них є спільна межа.