{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\n二进制编码十进制(BCD)是一种用于十进制数字的编码方式,其中每个数字由其自己的二进制序列表示。\n使用常见的BCD编码来编码十进制数,每个十进制数字都存储在一个4位的半字节中:\n\u003c/p\u003e\n\u003cpre\u003eDecimal: 0 1 2 3 4 5 6 7 8 9\nBCD: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001\n\u003c/pre\u003e\n\u003cp\u003e因此,数字127的BCD编码将是:\u003c/p\u003e\n\u003cpre\u003e 0001 0010 0111\n\u003c/pre\u003e\n\u003cp\u003e\n我们要将所有从 \u003ci\u003eA\u003c/i\u003e 到 \u003ci\u003eB\u003c/i\u003e 的整数转换为BCD代码。\n但我们发现一些连续的位,称为禁止码,可能会导致错误。如果某个整数的编码包含这些禁止码,则无法正确传输该整数。\n现在我们需要你的帮助来计算有多少个整数可以被正确传输。\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e输入\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n有多个测试用例。输入的第一行是一个整数 \u003ci\u003eT\u003c/i\u003e ≈ 100,表示测试用例的数量。\n\u003c/p\u003e\n\u003cp\u003e\n每个测试用例的第一行包含一个整数 \u003ci\u003eN\u003c/i\u003e,表示禁止码的数量(0 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100)。\n然后是 \u003ci\u003eN\u003c/i\u003e 行,每行包含一个长度不超过20的0-1字符串。\n接下来一行包含两个正整数 \u003ci\u003eA\u003c/i\u003e 和 \u003ci\u003eB\u003c/i\u003e。 \u003ci\u003eA\u003c/i\u003e 和 \u003ci\u003eB\u003c/i\u003e 都不包含前导零,且 0 \u0026lt; \u003ci\u003eA\u003c/i\u003e ≤ \u003ci\u003eB\u003c/i\u003e \u0026lt; 10\u003csup\u003e200\u003c/sup\u003e。\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e输出\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n对于每个测试用例,输出介于 \u003ci\u003eA\u003c/i\u003e 和 \u003ci\u003eB\u003c/i\u003e 之间的整数数量,它们的编码中不包含任何 \u003ci\u003eN\u003c/i\u003e 个禁止码。\n由于结果可能非常大,你只需要输出它 \u003cb\u003emod 1000000009\u003c/b\u003e 的值。\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e示例输入\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e3\n1\n00\n1 10\n1\n00\n1 100\n1\n1111\n1 100\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e示例输出\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e3\n9\n98\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e参考资料\u003c/b\u003e\u003c/p\u003e\n\n\u003cul\u003e\n\t\u003cli\u003e\u003ca href\u003d\"http://en.wikipedia.org/wiki/Binary-coded_decimal\" target\u003d\"_blank\"\u003ehttp://en.wikipedia.org/wiki/Binary-coded_decimal\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e"}}]}