회로 검사
시간 제한5초메모리 제한512 MB
N개의 변수가 각각 한 번씩만 나타나는 &, |, ~ 불리언 식이 주어질 때, 식을 참으로 만드는 변수 대입의 수를 1,000,000,007로 나눈 나머지로 구한다.
문제
불리언 식이 주어진다. 이 식에서 각 변수는 정확히 한 번씩 등장한다. 식이 참으로 계산되게 하는 변수 대입의 개수를 구하라.
입력
데이터 세트는 한 줄로만 이루어진다. 불리언 식은 숫자, x, (, ), |, &, ~로 이루어진 문자열로 주어진다. 공백 같은 다른 문자는 포함되지 않는다. 식의 길이는 1,000,000자를 넘지 않는다. 식의 문법은 다음 BNF로 주어진다.
<expression> ::= <term> | <expression> "|" <term>
<term> ::= <factor> | <term> "&" <factor>
<factor> ::= <variable> | " " <factor> | "(" <expression> ")"
<variable> ::= "x" <number>
<number> ::= "1" | "2" |... | "999999" | "1000000"
식은 이 문법을 따르므로 문법 오류는 고려하지 않아도 된다. 식에 N개의 변수가 있으면 {x1, x2,..., xN}의 각 변수는 정확히 한 번씩 등장한다.
출력
식을 참으로 계산되게 하는 변수 대입의 개수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.