子串

【题目描述】

给出一些字符和各自对应的选择概率，随机选择L次后将得到一个长度为L的随机字符串S（每次独立随机）。给出K个模板串，计算S不包含任何一个串的概率（即任何一个模板串都不是S的连续子串）。

【输入格式】

输入第一行为测试数据组数T(T<=50)。

对于每组测试数据，第一行为模板串个数K(K<=20)。以下K行每行包含一个模板串（长度不超过20）。接下来一行为一个整数N，即字符个数，下面的N行每行为一个不同的字符（保证为大小写字母或者数字）和选择它的概率pi。所有pi之和保证为1。最后一行为生成的字符串长度L（L<=100）。模式串保证只由上述N个字符组成。

每组测试数据结束后有一个空行。

【输出格式】

对于每组测试数据，先输出测试数据编号，再输出生成的串不包含任何一个模板串的概率，结果保留到小数点后6位（详细格式见样例输出）。

【样例输入】

2
1
a
2
a 0.5
b 0.5
2

2
ab
ab
2
a 0.2
b 0.8
2

【样例输出】

Case #1: 0.250000
Case #2: 0.840000

【提示】

在此键入。

【来源】

在此键入。