{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eNanjing University of Science and Technology is celebrating its 60th anniversary. In order to make room for student activities, to make the university a more pleasant place for learning, and to beautify the campus, the college administrator decided to start construction on an open space.\u003cbr\u003eThe designers measured the open space and come to a conclusion that the open space is a rectangle with a length of n meters and a width of m meters. Then they split the open space into n x m squares. To make it more beautiful, the designer decides to cover the open space with 1 x 1 bricks and 1 x 2 bricks, according to the following rules:\u003cbr\u003e\u003cbr\u003e1. All the bricks can be placed horizontally or vertically\u003cbr\u003e2. The vertexes of the bricks should be placed on integer lattice points\u003cbr\u003e3. The number of 1 x 1 bricks shouldn’t be less than C or more than D. The number of 1 x 2 bricks is unlimited.\u003cbr\u003e4. Some squares have a flowerbed on it, so it should not be covered by any brick. (We use 0 to represent a square with flowerbet and 1 to represent other squares)\u003cbr\u003e\u003cbr\u003eNow the designers want to know how many ways are there to cover the open space, meeting the above requirements.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases, please process till EOF.\u003cbr\u003eEach test case starts with a line containing four integers N(1 \u0026lt;\u003d N \u0026lt;\u003d 100), M(1 \u0026lt;\u003d M \u0026lt;\u003d 10), C, D(1 \u0026lt;\u003d C \u0026lt;\u003d D \u0026lt;\u003d 20). Then following N lines, each being a string with the length of M. The string consists of ‘0’ and ‘1’ only, where ‘0’ means the square should not be covered by any brick, and ‘1’ otherwise."}},{"title":"Output","value":{"format":"HTML","content":"Please print one line per test case. Each line should contain an integers representing the answer to the problem (mod 10\u003csup\u003e9\u003c/sup\u003e + 7)."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 0 0\r\n1\r\n1 1 1 2\r\n0\r\n1 1 1 2\r\n1\r\n1 2 1 2\r\n11\r\n1 2 0 2\r\n01\r\n1 2 0 2\r\n11\r\n2 2 0 0\r\n10\r\n10\r\n2 2 0 0\r\n01\r\n10\r\n2 2 0 0\r\n11\r\n11\r\n4 5 3 5\r\n11111\r\n11011\r\n10101\r\n11111\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n0\r\n1\r\n1\r\n1\r\n2\r\n1\r\n0\r\n2\r\n954\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}