{"trustable":false,"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":"MD","content":"给定一个 $n * m$ 的棋盘,两只乌龟一起从左上角出发,目标是右下角,每次可以向右或者向下走一步。 \n问有多少种方案,可以使得这两只乌龟在直到终点前的行进过程中**彼此不相遇**。\n\n---\n\n\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\n\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\n\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":"MD","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\n\u003cp\u003eIt is guaranteed that the upper left and the lower right cells are empty.\u003c/p\u003e"}},{"title":"Output","value":{"format":"MD","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":"Sample 1","value":{"format":"MD","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":"Sample 2","value":{"format":"MD","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"}}]}