B. Basic Equation Solving
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo recently saw some constraints in the form of $$$X\, op\, Y$$$ where $$$X$$$ and $$$Y$$$ are strings consisting of digits from $$$0$$$ to $$$9$$$ and uppercase English letters, denoting the decimal representation of a number and $$$op \in \{ \lt , \gt ,=\}$$$ denotes the operator. A solution to such a constraint is an assignment of $$$0-9$$$ to each of the $$$26$$$ uppercase English letters, such that all constraints are satisfied. Here, leading zeroes are allowed.

For example, suppose the constraint is $$$\text{P}=\text{NP}$$$. Then, the set of solutions satisfying this constraint is all assignments with $$$N=0$$$. Another example is the constraint $$$\text{2000CNY} \gt \text{3000USD}$$$. Here, no assignments can satisfy this constraint since $$$\text{2000CNY}$$$ is a $$$7$$$-digit decimal integer less than $$$3\times 10^6$$$, and $$$\text{3000USD}$$$ is a $$$7$$$-digit decimal integer greater than or equal to $$$3\times 10^6$$$.

Now Bobo has received a system of $$$n$$$ constraints, and he wonders how many assignments of $$$0-9$$$ to each of the $$$26$$$ uppercase English letters are there, such that all constraints are satisfied. Since the answer might be too large, you need to output the answer modulo $$$998\,244\,353$$$ (a prime number).

Input

The first line of input contains one integer $$$n$$$ $$$(0\leq n\leq 10)$$$, denoting the number of constraints.

Then, $$$n$$$ lines follow. Each line contains a constraint in the form of $$$X\, op \, Y$$$, where $$$X$$$ and $$$Y$$$ are strings consisting of digits from $$$0$$$ to $$$9$$$ and uppercase English letters and $$$op \in \{ \lt , \gt ,=\}$$$.

It is guaranteed that the sum of lengths over all constraints does not exceed $$$50$$$.

Output

Output one integer in a line, denoting the number of solutions to the given system of constraints, taken modulo $$$998\,244\,353$$$.

Examples
Input
1
P=NP
Output
766136394
Input
1
2000CNY>3000USD
Output
0
Input
4
AB>CD
E<A
BC>FF
EF>F1
Output
23645065
Note

As already discussed in the statement, the constraint $$$\text{P}=\text{NP}$$$ has $$$10^{25}$$$ solutions, which is $$$766136394$$$ after taken modulo $$$998\,244\,353$$$, and $$$\text{2000CNY} \gt \text{3000USD}$$$ has zero solutions.