{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou\u0027ve got a table of size \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e\u003c/span\u003e. We\u0027ll consider the table rows numbered from top to bottom 1 through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, and the columns numbered from left to right 1 through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e. Then we\u0027ll denote the cell in row \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and column \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e as \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eInitially cell \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e contains two similar turtles. Both turtles want to get to cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e. Some cells of the table have obstacles but it is guaranteed that there aren\u0027t any obstacles in the upper left and lower right corner. A turtle (one or the other) can go from cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e to one of two cells \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e + 1, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e + 1)\u003c/span\u003e, as long as the required cell doesn\u0027t contain an obstacle. The turtles have had an argument so they don\u0027t want to have any chance of meeting each other along the way. Help them find the number of ways in which they can go from cell \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e to cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eMore formally, find the number of pairs of non-intersecting ways from cell \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e to cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e modulo \u003cspan class\u003d\"tex-span\"\u003e1000000007\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7)\u003c/span\u003e. Two ways are called non-intersecting if they have exactly two common points — the starting point and the final point.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(2 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 3000)\u003c/span\u003e. Each of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e characters describing the table. The empty cells are marked by characters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e.\u003c/span\u003e\", the cells with obstacles are marked by \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e#\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eIt is guaranteed that the upper left and the lower right cells are empty.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn a single line print a single integer — the number of pairs of non-intersecting paths from cell \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e to cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e modulo \u003cspan class\u003d\"tex-span\"\u003e1000000007\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7)\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","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\u003e4 5\n.....\n.###.\n.###.\n.....\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e2 3\n...\n...\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}