#P18468. Basic Equation Solving

Basic Equation Solving

Basic Equation Solving

Bobo 最近看到一些形如 X op YX\ \mathrm{op}\ Y 的约束。其中 X,YX,Y 是由数字 0 到 9 和大写英文字母组成的非空字符串,表示一个十进制整数;op∈{<,>,=}\mathrm{op}\in\{<,>,=\} 是比较运算符。

一个约束的解,是给 26 个大写英文字母中的每一个赋一个 00 到 99 的数字,使该约束成立。允许前导零。不同字母可以赋相同的数字。

例如,约束 P=NP 的解是所有满足 N=0 的赋值。再如,约束 2000CNY>3000USD 没有解,因为前者总是小于 3×1063\times10^6 的七位十进制整数,后者总是不小于 3×1063\times10^6。

现在 Bobo 收到一个由 nn 个约束组成的系统。他想知道,有多少种给全部 26 个大写英文字母赋数字的方案,能使所有约束同时成立。答案可能很大,输出对质数 998244353998244353 取模后的结果。

输入格式

第一行包含一个整数 nn(0≤n≤100\le n\le10),表示约束数。

接下来 nn 行,每行给出一个形如 XopY 的约束,其中 X,YX,Y 由数字 0 到 9 和大写英文字母组成,op 是 <、>、= 之一。

保证所有约束的字符串长度之和不超过 5050。

输出格式

输出一个整数,表示满足整个约束系统的赋值方案数对 998244353998244353 取模的结果。

原样例 1 输入

1
P=NP

原样例 1 输出

766136394

原样例 2 输入

1
2000CNY>3000USD

原样例 2 输出

0

原样例 3 输入

4
AB>CD
E<A
BC>FF
EF>F1

原样例 3 输出

23645065

样例说明

如前所述,P=NP 恰好要求 N=0,共有 102510^{25} 个解,取模后是 766136394766136394;2000CNY>3000USD 没有解。