Татьяна Олеговна делает брелоки из бисера. Брелоки представляют собой нить, на которую нанизаны 12 бусин. Татьяна использует только белые, серые и чёрные бусины. С одной стороны этой нити расположено крепление для ключей. Раньше Татьяна записывала схемы брелоков с помощью последовательностей нулей, единиц и двоек, где «0» означал белую бусину, «1» — чёрную, а «2» — серую. Крепление для ключей всегда предполагается в левой части схемы.
Пример схемы брелока, состоящего из 10 чёрных бусин и 2 белых, в котором часть брелока, ближайшая к креплению, чёрная, а вторая часть — белая: 111111111100 — итого запись содержит 12 символов, по одному на каждую бусину.
Но вот однажды Татьяна придумала, как можно сократить запись: вместо того, чтобы записывать подряд 10 «1», она решила записывать число бусин одного цвета, которые идут подряд (например, 10), ставить дефис «-», после чего записывать цвет бусинки («1» — чёрный, «0» — белый, «2» — серый). Между такими блоками ставится запятая. Подряд не может записываться два блока, описывающих бусины одного и того же цвета, — они должны быть объединены в один блок. В блоке не может быть 0 или отрицательное число бусин. Таким образом, запись схемы брелока из примера выше сокращается до 10-1,2-0 — итого 8 символов, что на 4 символа меньше исходной записи.
Однако выяснилось, что в некоторых случаях новая запись становится даже длиннее, чем исходная, например брелок из чередующихся белых и чёрных бусин. Исходная форма записи: 010101010101 — 12 символов. Новая форма записи: 1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1 — 47 символов.
Сколько существует различных брелоков длины 12, схемы которых в новой и исходной формах записи содержат по одинаковому количеству символов? Брелоки считаются различными, если отличаются хотя бы одной бусиной. В ответ запишите одно число — количество брелоков.