Let ~X~ represent a non-negative integer strictly less than ~2^{60}~.

You are given a list of ~N~ constraints on ~X~.

Each constraint is a bitwise operator followed by two numbers: the second input and the output of the bitwise operation.

Any of the following bitwise operators may appear in a given constraint: AND, OR, NAND, NOR.

For example, a constraint could be AND 7 3, meaning that ~X \land 7 = 3~.

How many solutions for ~X~ satisfy all ~N~ constraints?

Input Specification

The first line contains an integer ~N~ ~(1 \le N \le 100)~.

The next ~N~ lines each contain the name of the bitwise operator followed by two integers ~Y~ and ~Z~ ~(0 \le Y, Z < 2^{60})~.

Output Specification

Output the number of solutions for ~X~ that satisfy all ~N~ constraints.

Sample Input 1

1
AND 0 1

Sample Output 1

0

Sample Input 2

4
AND 1 1
OR 12287 16383
NAND 6 1152921504606846975
NOR 1152921504606844927 0

Sample Output 2

512