{"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\nBinary-coded decimal (BCD) is an encoding for decimal numbers in which each digit is represented by its own binary sequence.\nTo encode a decimal number using the common BCD encoding, each decimal digit is stored in a 4-bit nibble:\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\u003eThus, the BCD encoding for the number 127 would be:\u003c/p\u003e\n\u003cpre\u003e 0001 0010 0111\n\u003c/pre\u003e\n\u003cp\u003e\nWe are going to transfer all the integers from \u003ci\u003eA\u003c/i\u003e to \u003ci\u003eB\u003c/i\u003e, both inclusive, with BCD codes.\nBut we find that some continuous bits, named forbidden code, may lead to errors. If the encoding of some integer contains these forbidden codes, the integer can not be transferred correctly.\nNow we need your help to calculate how many integers can be transferred correctly.\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nThere are multiple test cases. The first line of input is an integer \u003ci\u003eT\u003c/i\u003e ≈ 100 indicating the number of test cases.\n\u003c/p\u003e\n\u003cp\u003e\nThe first line of each test case contains one integer \u003ci\u003eN\u003c/i\u003e, the number of forbidden codes ( 0 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100).\nThen \u003ci\u003eN\u003c/i\u003e lines follow, each of which contains a 0-1 string whose length is no more than 20.\nThe next line contains two positive integers \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e. Neither \u003ci\u003eA\u003c/i\u003e or \u003ci\u003eB\u003c/i\u003e contains leading zeros and 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\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nFor each test case, output the number of integers between \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e whose codes do not contain any of the \u003ci\u003eN\u003c/i\u003e forbidden codes in their BCD codes.\nFor the result may be very large, you just need to output it \u003cb\u003emod 1000000009\u003c/b\u003e.\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input\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\u003eSample Output\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\u003eReferences\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\n\n\n"}}]}