비밀번호

새 비밀번호를 정해야 한다. 시스템 관리자가 정한 규칙은 다음과 같다.

• 영문자와 숫자만 쓸 수 있다.
• 길이는 $A$자 이상 $B$자 이하다.
• 소문자, 대문자, 숫자를 각각 최소 한 개씩 포함해야 한다.
• 금지 단어 목록(블랙리스트)에 있는 단어를 포함할 수 없다.

블랙리스트의 단어가 비밀번호 안에서 연속한 문자열로 나타나면 그 단어를 포함한 것으로 본다. 이때 대소문자는 구분하지 않는다. 예를 들어 swerc는 SwErC, 2016swerc2016, SWERC2016의 부분 문자열이지만 ICPC나 sw16erc의 부분 문자열은 아니다.

숫자를 글자 대신 쓴 표기도 걸러낸다. 0은 o, 1은 i, 3은 e, 5는 s, 7은 t로 읽는다. 그래서 5w3rC는 swerc가 나타난 것으로 보고, abcL337def는 leet를 포함한다. 숫자 2, 4, 6, 8, 9는 어떤 글자로도 읽지 않는다.

블랙리스트 단어 $N$개와 두 정수 $A$, $B$가 주어진다. 규칙을 모두 지키는 서로 다른 비밀번호의 개수를 구하라. 개수가 매우 클 수 있으므로 1000003으로 나눈 나머지를 출력한다.

첫째 줄에 비밀번호의 최소 길이 $A$와 최대 길이 $B$가 주어진다. 둘째 줄에 블랙리스트 단어의 개수 $N$이 주어진다. 이어지는 $N$개 줄에 블랙리스트 단어 $W_i$가 한 줄에 하나씩 주어진다. 각 단어는 영어 소문자로만 이루어진다.

유효한 비밀번호의 개수를 1000003으로 나눈 나머지를 한 줄에 출력한다.

• $3 \le A \le B \le 20$
• $0 \le N \le 50$
• $1 \le |W_i| \le 20$