Proof of Knowledge

Time limit8sMemory limit512 MB

Summary

Parse a small expression tree over four bit variables a-d, evaluate it for a given 4-digit password, and count how many of the 10000 passwords yield the same bit.

Level: Medium4 of 10
Topics: Implementation, Recursion, Brute force, String matching
Solved: No attempts yet

Problem

The entrance door of the apartment building where you live has a password lock. The password consists of exactly 4 digits, each from 0 to 9, and you always unlock the door using the password P that the building manager gave you.

One day you wonder whether all the residents use the same password P as you, so you decide to ask a friend who lives in the same building. You and your friend can check whether you use the same password by telling each other your passwords. But since each resident may have been assigned a separate password, this method is not desirable. Only you should know your own password, and you should not tell it to others.

To avoid this, you and your friend decide to input your passwords into a hash function and tell each other the resulting hash values. The formula S of the hash function used here consists of the lowercase letters 'a', 'b', 'c', 'd' and the symbols '[', ']', '+', '*', '^', and is represented by <Hash>, defined by the following BNF.

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

Here 'a', 'b', 'c', 'd' denote the first, second, third, and fourth digits of the 4-digit password. '+', '*', '^' are operators with the following meanings.

'+' : take the logical OR of the two following <Hash> values written in binary
'*' : take the logical AND of the two following <Hash> values written in binary
'^' : take the logical XOR of the two following <Hash> values written in binary

The truth tables of logical OR, logical AND, and logical XOR are as follows.

A	B	[+AB]
0	0	0
1	0	1
0	1	1
1	1	1

A	B	[*AB]
0	0	0
1	0	0
0	1	0
1	1	1

A	B	[^AB]
0	0	0
1	0	1
0	1	1
1	1	0

For example, inputting the password 0404 into the hash function [+c[+a[^bd]]] gives the hash value 0. Passwords that give the same hash value include 0000, 0101, 0202, 0303, 0505, 0606, 0707, 0808, 0909.

Output the result of inputting your password P into the hash function S. Also, to prevent the use of a hash function from which the password can be uniquely determined from the hash value, output the number of passwords that give the same hash value as your password.

Input

The input consists of at most 50 datasets. Each dataset has the following format.

S
P

The first line of each dataset is the formula S of the hash function. The second line of each dataset is the password P, which has 4 digits, each from 0 to 9. You may assume the length of the hash function S is at most 80.

The end of the input is indicated by a line containing only the single character '.'.

Output

For each dataset, output the hash value obtained by inputting P into S, and the number of passwords that give the same hash value as P, separated by a space.

Examples1

Example 1

Input

[+c[+a[^bd]]]
0404
[*b[*[*cd]a]]
7777
[^[^ab][^cd]]
1295
a
9876
[^dd]
9090
.

Expected output