又到了每年一度的工作时间，你需要为你的所有服务选择新的密码。系统管理员强制执行的规则非常严格，你选择的密码必须遵守以下限制：

• 必须仅包含字母和数字。
• 长度必须在 $A$ 到 $B$ 之间（包含 $A$ 和 $B$）。
• 必须至少包含一个小写字母、一个大写字母和一个数字。
• 不能包含黑名单中的任何单词。

如果黑名单中的某个单词作为子串出现在密码中，则认为该密码包含该单词。也就是说，如果它作为连续的字符序列出现（不区分大小写）。例如，swerc 是 SwERC、2016swerc2016 或 SWERC16 的子串，但不是 ICPC 或 sw16erc 的子串。

此外，为了规避黑名单，你不能使用 l33t 风格的写法。具体来说，某些数字可以被解释为字母，即 0（'o'）、1（'i'）、3（'e'）、5（'s'）和 7（'t'）。这意味着例如 5w3rC 会被视为出现了 swerc，而 abcL337def 包含单词 leet。

你无法停止思考所有这些规则，并想知道到底有多少种不同的有效密码……你能计算出有多少个密码符合这些规则吗？

给定一个包含 $N$ 个单词的黑名单和两个整数 $A$ 和 $B$，你的任务是计算符合给定约束的有效密码的数量：仅由字母和数字组成；长度在 $A$ 到 $B$ 之间（包含 $A$ 和 $B$）；至少包含一个小写字母、一个大写字母和一个数字；不包含任何黑名单中的子串。由于这个数字可能非常大，请计算其对 $1\,000\,003$ 取模的结果。

输入格式

第一行包含两个整数 $A$ 和 $B$，分别指定密码的最小和最大长度。第二行包含一个整数 $N$，表示黑名单中单词的数量。接下来的 $N$ 行，每行包含一个字符串 $W_i$，表示黑名单中的一个单词。这些单词仅由小写字母组成。

数据范围

$3 \le A \le B \le 20$ $0 \le N \le 50$ $1 \le \text{length}(W_i) \le 20$

输出格式

输出包含一行，为一个整数，表示符合所有给定约束的有效密码数量对 $1\,000\,003$ 取模的结果。

样例

输入格式 1

3 5
9
swerc
icpc
fbi
cia
bio
z
hi
no
yes

输出格式 1

607886

说明

在这种情况下，共有 $378\,609\,020$ 个有效密码，且 $$378\,609\,020 \pmod{1\,000\,003} = 607\,886$$

有效密码的一些例子：aA1、B23tT、1g9K 或 B2j。 无效密码的一些例子：aaA（不包含数字）、12a（不包含大写字母）、a12A34（长度 > 5）或 bB10（包含 bio 作为子串）。