Резкое увеличение количества машин в стране привело к нехватке автомобильных номеров. Для разработки формата нового номера была создана комиссия, которая пришла к выводу, что: \begin{itemize} \item номер должен состоять из \textbf{m} символов; \item для обеспечения простоты запоминания номера все допустимые в номере символы должны быть разбиты на группы (например, буквы и цифры). Один и тот же символ не может входить в несколько групп; \item символы, принадлежащие каждой из групп, должны располагаться в строго отведенных местах, заданных маской (например, для маски "бцццбб" где \textbf{б} -- это символ из группы букв, а \textbf{ц} -- символ из группы цифр, допустимым будет номер "в264ро"); \item в номере не может быть двух одинаковых символов для обеспечения отсутствия "красивых" номеров. \end{itemize} Требуется по списку групп символов и маске их расположения в номере определить максимальное количество номеров, которые могут быть созданы. \InputFile Первая строка содержит одно целое число \textbf{n} -- количество групп символов (\textbf{1} ≤ \textbf{n} ≤ \textbf{9}). Следующие \textbf{n} строк содержат описания групп символов. Каждая строка состоит из двух целых чисел \textbf{k} и \textbf{c}, разделенных пробелом, где \textbf{k} -- номер группы символов (\textbf{1} ≤ \textbf{k} ≤ \textbf{n}), а \textbf{c} -- количество символов в группе (\textbf{1} ≤ \textbf{c} ≤ \textbf{15}). Последняя строка содержит маску номера, в которой каждая цифра определяет номер группы, символ из которой должен располагаться в указанном месте. Строка имеет хотя бы один символ и ее длина не превышает \textbf{15} символов. Гарантируется, что каждая цифра в строке находится в диапазоне от \textbf{1} до \textbf{n}. \OutputFile Выходной файл должен содержать одно целое число -- максимальное количество номеров, которые могут быть созданы для заданных условий. Если ни один номер не может быть создан, то вывести \textbf{0}.