J. BCD码
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
二进制编码的十进制（BCD）是一个为自己的二进制序列，其中每个数字代表十进制数的编码。编码使用常见的BCD编码的十进制数，每个十进制数字存储在一个4位的四位：
因此，为编号127的BCD编码将是：
0001 0010 0111
我们要通过BCD码传输所有从A到B的整数（包括A和B），但是我们发现一些连续的位（本题叫禁码）可能导致错误。如果这些整数的编码包括 禁码, 那么这些整数不能正确的传输。现在，我们需要你的帮助来计算多少整数，可以正确传输。
因此，为编号127的BCD编码将是：
0001 0010 0111
我们要通过BCD码传输所有从A到B的整数（包括A和B），但是我们发现一些连续的位（本题叫禁码）可能导致错误。如果这些整数的编码包括 禁码, 那么这些整数不能正确的传输。现在，我们需要你的帮助来计算多少整数，可以正确传输。
Input
有多组测试用例。输入的第一行是一个整数T≈100表示测试用例的数量。
每个测试用例的第一行包含一个整数N，表示禁码的个数（0≤ N ≤100）。
接下来的N行，其中每个都包含一个0-1的字符串，其长度不超过20。
下一行包含两个正整数A和B（十进制表示）。A 和B 都不包含前导零，并且满足0 < A ≤ B < 10200。
每个测试用例的第一行包含一个整数N，表示禁码的个数（0≤ N ≤100）。
接下来的N行，其中每个都包含一个0-1的字符串，其长度不超过20。
下一行包含两个正整数A和B（十进制表示）。A 和B 都不包含前导零，并且满足0 < A ≤ B < 10200。
Output
对于每个测试用例，输出A到B之间（包括A和B）不包含这N个禁码的整数的个数。结果可能是非常大的，你只需要输出模1000000009。
Sample Input
3 1 00 1 10 1 00 1 100 1 1111 1 100
Sample Output
3 9 98
Author
Source
developing schools contest 5