Super Poker II

有一副无限大的超级扑克牌。对于每个正合数 $p$ ，牌组中恰好有四张点数为 $p$ 的牌，花色分别为黑桃（S）、红桃（H）、梅花（C）和方块（D）。牌组中不存在点数为其他数的牌。

正合数是指约数个数多于 $2$ 的正整数。例如， $6$ 有 $1,2,3,6$ 共 $4$ 个约数，因此 $6$ 是合数； $7$ 只有 $1,7$ 共 $2$ 个约数，因此 $7$ 不是合数。特别地， $1$ 只有 $1$ 个约数，也不是合数。

给定一个正整数 $n$ ，需要从每种花色中恰好选出一张牌，即分别选出一张黑桃、一张红桃、一张梅花和一张方块，使这四张牌的点数之和等于 $n$ 。例如，当 $n=24$ 时， $4\mathrm{S}+6\mathrm{H}+4\mathrm{C}+10\mathrm{D}$ 是一种选法。

牌组中的部分牌已经遗失，不能再被选取。现在给定两个正整数 $a$ 和 $b$ ，请分别求出当 $n=a,a+1,\ldots,b$ 时，满足条件的选牌方案数。

输入格式

输入包含不超过 $25$ 组测试数据。

每组测试数据的第一行包含三个整数 $a,b,c$ ，其中 $c$ 表示遗失牌的数量。

下一行包含 $c$ 个字符串，表示遗失的牌。每张牌表示为 valueS、valueH、valueC 或 valueD，其中 value 是满足 $4\le \mathrm{value}\le 5\times 10^4$ 的合数，末尾字母表示花色。任意两张遗失的牌互不相同。

输入以 $a=b=c=0$ 结束，这一行不属于任何测试数据。

至多有一组测试数据满足 $a=1$ 、 $b=5\times 10^4$ 且 $c\le 10^4$ 。对于其他测试数据，满足 $1\le a\le b\le 100$ 且 $0\le c\le 10$ 。

对于每组测试数据，依次输出 $b-a+1$ 个整数，每个整数占一行，分别表示 $n=a,a+1,\ldots,b$ 时的选牌方案数。

由于答案可能很大，请将每个答案对 $10^6$ 取模后输出。

每组测试数据输出结束后，再输出一个空行。

12 20 2
4S 6H
0 0 0

本题为湖南省第七届大学生程序设计大赛试题「Super Poker II」，题面与测试数据整理自 BZOJ。

12 20 2
4S 6H
0 0 0