Formula Equivalence

A propositional formula is generated by the following grammar.

 <formula> ::= <variable> | ~<formula> | ( <formula> ) | <formula> <operator> <formula>
<operator> ::= ^ | V
<variable> ::= one letter from a-z or A-Z, except the character V

^ is boolean AND, V is boolean OR, and ~ is boolean NOT.

An interpretation assigns true or false to every variable that occurs in a formula. Once an interpretation is fixed, the truth value of the formula follows from applying the boolean operations to the variable values in the standard way.

Two formulae are equivalent if they produce the same truth value under every possible interpretation. An interpretation here assigns a value to every variable that occurs in either of the two formulae.

Given two formulae, decide whether they are equivalent.

The first line holds one formula and the second line holds the other. A variable is a single letter, and the character V is reserved for the OR operator, so it is never a variable name. Whitespace can occur anywhere inside a line.

Each line is at most 1000 characters including whitespace, and the two formulae together use at most 16 distinct variables.

Print 1 if the two formulae are equivalent, and 0 otherwise.

~ applies to the single term right after it and binds more tightly than ^ and V. ^ and V have the same precedence and group from the left. For example, x ^ y V z is the same as (x ^ y) V z, and ~x ^ y is the same as (~x) ^ y.