Задача №112679. Гравицапа: инструкция по применению
Если бы кто-нибудь на Плюке точно знал, как устроена гравицапа, их изготовление можно было бы наладить на Плюке. А сейчас гравицацы приходится закупать на соседней планете, а это очень хлопотно и дорого. Плюканам только отчасти известна её управляющая система. Но этого вполне достаточно, чтобы самим строить совместимые с гравицапами пепелацы. Согласитесь, это тоже очень важно!
Недавно плюканские исследователи гравицап обнаружили, что время от времени гравицапа генерирует сигнал из \(N\) битов. Когда плюкане начали разбираться, откуда он берётся, выяснилось следующее:
1) Внутри гравицапы есть модуль, который по неизвестным науке алгоритмам генерирует набор из 2\(N\) битов.
2) Этот сигнал передаётся на вход Преобразователю. Преобразователь содержит в себе таблицу с \(R\) правилами. Каждое правило - последовательность из \(N\) символов "&", "|", "^".
3) Преобразователь выбирает произвольным образом одно правило из таблицы и применяет его к входной последовательности. Операция, соответствующая первому символу правила, применяется к первым двум битам входной последовательности, а её результат - первый бит выходной последовательности. Операция, соответствующая второму символу, применяется ко второй паре входных битов и формирует второй выходной, и так далее. Ниже приведены таблицы значений операций, соответствующих этим символам:
Например, 0 & 1 = 0, 1 ^ 0 = 1.
Таким образом, из входной последовательности из 2\(N\) битов формируется выходная последовательность из \(N\) битов. К сожалению, неизвестно, какое именно правило было выбрано для преобразовании. Ваша задача - зная выходную последовательность и набор правил, определить количество различных входных последовательностей, из которой могла получиться выходная.
Пусть, например, \(N\)=2, \(R\)=2, выходная последовательность {1, 1}, а таблица правил имеет вид:
первое правило & &
второе правило | &
Тогда любой набор из четырех битов будет преобразован следующим образом:
Тогда последовательность "11" могла получиться из трех входных последовательностей.
В первой строке два целых числа - \(N\), \(R\). (1 ≤ \(N\) ≤ 18, 1 ≤ \(R\) ≤ 50). Во второй строке - строка длины \(N\), состоящая из символов 0 и 1 - выходная последовательность. В каждой из последующих \(R\) строк - строка длины \(N\) из символов &, |, ^ - очередная строка таблицы правил.
Выведите одно число - количество различных входных последовательностей, из которых могла получиться заданная выходная последовательность в результате применения некоторого правила.
2 2 11 && |&
3
18 1 111111111111111111 ||||||||||||||||||
387420489