Одним из способов проведения какого-либо турнира является формат playoff. В турнире участвуют N = 2^k команд. В самом начале команды разбиваются на пары, победители в каждой паре проходят дальше по турнирной сетке, играя по аналогичным правилам для вдвое меньшего количества игроков, а проигравшие занимают низ итоговой таблицы. Заметим, что победитель последней встречи является победителем всего турнира.

Одним из минусов этой системы является неполная объективность результатов: не все команды играют между собой для определения чемпиона. Для того, чтобы занять первое место, нужно выиграть всего лишь k встреч. Из-за этого высока непредсказуемость результатов и всё зачастую зависит от изначального расположения команд на старте турнира.

Вы работаете в организации, которая собирается провести крупный турнир. Начальство хочет выбрать стартовую расстановку лично. Для удобства, названия команд заменены на уникальный номер от 1 до N, а расстановка записывается как последовательность этих чисел. Специальный менеджер уже подготовил M вариантов расстановок, но за миг до то того, как предоставить их для рассмотрения обнаружил, что некоторые из них являются эквивалентными. Допустим, мы будем знать исход встречи для каждой возможной пары команд. Тогда, две стартовые расстановки называются эквивалентными, если итоговые таблицы этих сеток совпадут. Матчи, сыгранные в этих сетках, будут одни и те же, возможно, в другом порядке.

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