이진수 복면산 해독

이진수로 쓰인 등식이 암호로 바뀌었다. 암호문을 보고 원래 등식이 몇 가지였을 수 있는지 센다.

원래 등식에 쓰이는 문자는 이진 숫자 0과 1, 연산자 +, -, *, 괄호 (와 ), 등호 =뿐이다. 암호화는 등식에 나온 문자 중 일부를 알파벳 글자로 바꾼다. 같은 문자를 바꿀 때는 언제나 같은 글자를 쓰고, 서로 다른 두 문자를 같은 글자로 바꾸는 일은 없다. 한 문자가 여러 번 나오더라도 모두 바꿀 필요는 없어서, 어떤 자리는 글자로 바뀌고 다른 자리는 원래 문자 그대로 남을 수 있고, 한 번도 바뀌지 않는 문자도 있을 수 있다. 바꿀 때 쓰는 글자는 로마자 대문자와 소문자 모두 가능하며 대소문자를 구별한다. 즉 a와 A는 다른 글자다. 숫자뿐 아니라 연산자, 괄호, 등호도 바뀔 수 있다.

등식은 다음 문맥 자유 문법의 시작 기호 Q에서 유도된다.

Q ::= E=E
E ::= T | E+T | E-T
T ::= F | T*F
F ::= N | -F | (E)
N ::= 0 | 1B
B ::= ε | 0B | 1B

여기서 ε는 빈 문자열을 뜻한다.

문법에서 보듯 등식에는 등호가 정확히 하나 있고, 양변은 수와 덧셈, 뺄셈, 곱셈, 부호 반전으로 이루어진 식이다. 곱셈은 덧셈과 뺄셈보다 먼저 계산하고, 부호 반전은 곱셈보다 먼저 계산한다. 곱셈, 덧셈, 뺄셈은 모두 왼쪽 결합이라서 x-y+z는 (x-y)+z이지 x-(y+z)가 아니다. 수는 0과 1을 늘어놓은 이진 표기이고, 두 자리 이상인 수는 반드시 1로 시작한다. 괄호와 부호 반전은 ((--x+y))+z처럼 필요 없이 여러 번 나타나도 된다.

암호문이 주어지면 그 암호문으로 암호화될 수 있는 올바른 등식이 몇 가지인지 센다. 등식이 올바르다는 것은 문법에 맞으면서 양변의 값이 같다는 뜻이다.

암호문이 ACM이면 등식에는 두 식 사이에 =가 하나 있어야 하므로 C는 =다. A와 M은 서로 다른 글자라서 서로 다른 문자를 나타내고, 한 글자씩인 양변의 값이 같아지는 경우는 없다. 암호문이 icpc이면 올바른 등식은 -0=0 하나뿐이다. 암호문이 BAYL0R이면 0=-(0), 0=(-0), -0=(0) 세 가지가 올바른 등식이다. 암호문에 있는 두 개의 0 가운데 하나는 글자로 바뀌지 않았다는 점에 주의한다.

첫째 줄에 암호문이 주어진다. 암호문은 로마자, 이진 숫자, 연산자 기호, 괄호, 등호로 이루어진 문자열이고 길이는 1 이상 31 이하다.

입력으로 주어진 문자열로 암호화될 수 있는 올바른 등식의 개수를 한 줄에 출력한다.