지식의 증명

당신이 사는 공동 주택 입구의 문에는 비밀번호식 잠금장치가 달려 있다. 이 비밀번호는 정확히 4자리이며 각 자리는 0부터 9까지의 숫자로 이루어져 있고, 당신은 항상 관리인에게서 전달받은 비밀번호 P 로 이 문의 잠금을 해제한다.

어느 날 당신은 주민 모두가 자신과 같은 비밀번호 P 를 쓰는지 궁금해져서, 같은 공동 주택에 사는 친구에게 물어보기로 했다. 당신과 친구는 서로 자신의 비밀번호를 알려 주면 같은 비밀번호를 쓰는지 확인할 수 있다. 하지만 비밀번호가 주민마다 따로 부여되었을 가능성을 생각하면 이 방법은 바람직하지 않다. 자신의 비밀번호를 아는 사람은 자기뿐이어야 하고, 남에게 알려서는 안 되기 때문이다.

이를 막기 위해 당신과 친구는 자신의 비밀번호를 해시 함수에 넣고, 얻은 해시값을 서로에게 알려 주기로 했다. 여기서 사용하는 해시 함수의 계산식 S 는 소문자 알파벳 'a', 'b', 'c', 'd' 와 기호 '[', ']', '+', '*', '^' 로 이루어지며, 아래 BNF로 정의되는 <Hash>로 나타낸다.

<Hash> ::= <Letter> | '['<Op><Hash><Hash>']' <Op> ::= '+' | '*' | '^' <Letter> ::= 'a' | 'b' | 'c' | 'd'

여기서 'a', 'b', 'c', 'd' 는 각각 4자리 비밀번호의 첫 번째, 두 번째, 세 번째, 네 번째 자리 숫자를 나타낸다. '+', '*', '^' 는 연산자이며 다음과 같은 뜻을 가진다.

• '+' : 뒤따르는 두 <Hash>를 이진수로 나타냈을 때의 논리합을 취한다
• '*' : 뒤따르는 두 <Hash>를 이진수로 나타냈을 때의 논리곱을 취한다
• '^' : 뒤따르는 두 <Hash>를 이진수로 나타냈을 때의 배타적 논리합을 취한다

여기서 논리합, 논리곱, 배타적 논리합의 진리표는 각각 다음과 같다.

예를 들어 해시 함수 [+c[+a[^bd]]]에 비밀번호 0404를 넣으면 해시값으로 0이 나온다. 같은 해시값이 나오는 비밀번호로 0000, 0101, 0202, 0303, 0505, 0606, 0707, 0808, 0909가 있다.

당신의 비밀번호 P 를 해시 함수 S 에 넣은 결과를 출력하라. 또한 해시값으로 비밀번호를 유일하게 알아낼 수 있는 해시 함수의 사용을 막기 위해, 당신의 비밀번호와 같은 해시값이 나오는 비밀번호의 개수도 출력하라.

입력은 최대 50개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 나타낸다.

S
P

각 데이터 세트의 첫째 줄은 해시 함수의 계산식 S 이다. 각 데이터 세트의 둘째 줄은 4자리이며 각 자리가 0부터 9까지의 숫자로 이루어진 비밀번호 P 이다. 해시 함수 S 의 길이는 80 이하라고 가정해도 된다.

입력의 끝은 '.' 한 글자만 포함하는 줄로 나타낸다.

각 데이터 세트에 대해, P 를 S 에 넣어 얻은 해시값과 P 와 같은 해시값이 나오는 비밀번호의 개수를 공백으로 구분해 출력하라.