#133. T1-徐老师点名了

T1-徐老师点名了

在信息学课上,徐老师要按照份“名单”点名。名单里有 nn 个候选字符串名字 T1,T2,,TnT_1, T_2, \dots, T_n。 他原本准备用一个目标字符串 SS 来精确匹配,但由于录入失误,SS 的某些位置被没写清楚,变成了 # —— 导致这些位置看不清究竟是哪一个小写字母。

我们说某个字符串 TiT_i 可能与 SS 相同,当且仅当:把 SS 中所有 # 位置分别替换为某个小写字母后,能使其与 TiT_i 在每一位都完全一致。 (特别地,若 TiS|T_i|\neq |S|,则无论如何替换都不可能相同。)

现在,请你告诉徐老师:名单里共有多少个字符串可能SS 相同。

输入格式

  • 第一行:一个字符串 SS。其中 # 表示该位置不确定,可替换为任意小写字母 az;其余已知位置均为小写字母。
  • 第二行:一个正整数 nn,表示名单中字符串的数量。
  • 接下来 nn 行:第 ii 行给出一个字符串 TiT_i。保证所有 TiT_i 均由小写字母组成。

输出格式

输出一行一个整数,表示有多少个 TiT_i 可能与 SS 相同。

样例

##c
3
abc
bbc
acb
2

样例解释

SS 的前两位是 #(可任意小写字母),第三位为 c。 候选串依次为 abcbbcacb。前两者的第三位都是 c,可以通过合适替换使之与 SS 完全一致;第三个字符串第三位为 b,无法匹配。因此答案为 22

数据范围

对于 100% 100\% 的数据,保证 2n20000 2 \le n \le 20000,所有字符串长度不超过 100 100

其它数据规模与约定如下表:

测试点 nn 特殊性质
121 \sim 2 =2=2
343 \sim 4 10 \le 10
565 \sim 6 2×104 \le 2 \times 10^4 SS 中至多只有 22#
787 \sim 8 所有字符串长度相等
9109 \sim 10