В данной задаче рассматриваются булевы функции от четырех переменных A, B, С, D. Переменные A, B, C и D являются логическими и могут принимать значения 0 или 1. Будем задавать функцию с помощью следующей грамматики:

<выражение> ::= <переменная> | (<выражение>) <оператор> (<выражение>)

<переменная> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

<оператор> ::= '&' | '|'

Здесь заглавными буквами A, B, C, D обозначаются переменные, а строчными — их отрицания. Например, если A = 1, то символу 'A' соответствует значение 1, а символу 'a' — значение 0. Символ '&' здесь соответствует операции логического И, символ '|' — операции логического ИЛИ.

Вам дано выражение s, задающее функцию f, в котором некоторые операторы и переменные пропущены. Так же вам известны значения функции f(A, B, C, D) для некоторых n различных наборов значений переменных. Посчитайте количество способов восстановить пропущенные в выражении элементы так, чтобы получившееся выражение соответствовало известной информации о функии f в заданных наборах переменных. Так как величина результата может быть большой, выведите её остаток от деления на 10⁹ + 7.