중요한 배선

컴퓨터 메인보드에는 여러 개의 중요한 배선(wire) 이 있으며, 각 배선은 두 가지 이진 상태 중 하나를 가진다: 활성(true) 또는 비활성(false). 배선의 이름은 소문자 a부터 k까지이며, 따라서 배선은 최대 11개다.

배선은 직접 관찰할 수 없다. 대신 유지보수 소켓에 여러 개의 출력 핀(pin) 이 노출되어 있고, 각 핀의 이름은 대문자다. 모든 핀은 집적 회로로 구동되므로, 그 상태는 배선 상태들에 대한 고정된 불(Boolean) 함수이며, 배선들에 대한 불 수식으로 주어진다.

수식은 아래 구성 요소로 이루어지며, 우선순위가 높은 것부터 낮은 것 순서로 나열하면 다음과 같다:

• 원자(Atom) — 배선 이름(소문자 a..k). 값은 해당 배선의 상태다.
• 괄호 — E가 수식이면 (E)도 수식이다.
• 부정(Negation) — ~E (우선순위가 가장 높은 연산자).
• 논리곱(Conjunction) — E1 & E2 & ... & En.
• 논리합(Disjunction) — E1 | E2 | ... | En.
• 함의(Implication) — E1 => E2 => ... => En. 오른쪽에서 왼쪽으로 계산하므로 E1 => E2 => E3은 E1 => (E2 => E3)을 뜻한다.
• 동치(Equivalence) — E1 <=> E2 <=> ... <=> En. 정의는 (E1 <=> E2) & (E2 <=> E3) & ... & (E(n-1) <=> En)이다.

배선들이 가능한 모든 이진 상태를 취할 때, 핀들은 여러 가지 상태 조합을 갖게 된다. 이때 나타날 수 있는 서로 다른 핀 상태 조합의 개수를 구하여라.

정확히 말하면, 입력에 주어진 순서대로 핀들을 P1, ..., Pn이라 하자. 배선에 활성/비활성 상태를 하나 배정할 때마다 모든 핀의 상태가 결정되어 하나의 튜플 (P1, ..., Pn)이 얻어진다. 수식에 등장하는 배선의 개수를 w라 할 때, 배선 배정이 가능한 2^w가지 경우를 모두 훑는 동안 얻어지는 서로 다른 튜플의 개수를 출력하여라.

첫 번째 줄에는 출력 핀의 개수를 나타내는 정수 n이 주어진다 (1 <= n <= 10).

이어지는 n개의 줄은 각각 하나의 핀을 설명하며, 대문자 핀 이름, 토큰 :=, 그리고 핀의 수식으로 구성된다. 수식은 토큰 a..k, (, ), ~, &, |, =>, <=>, 그리고 공백으로 이루어진 문자열이다. 여기서 ~, &, |, =>, <=>는 각각 부정, 논리곱, 논리합, 함의, 동치를 나타낸다. 토큰은 임의 개수의 공백으로 구분될 수 있으며, 각 줄의 길이는 최대 1000자다. 핀 이름은 서로 다르다.

배선이 가능한 모든 이진 상태를 취할 때 나타날 수 있는 서로 다른 핀 상태 조합의 개수를 정수 하나로 출력하여라.