{"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\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePeppa the Pig was walking and walked into the forest. What a strange coincidence! The forest has the shape of a rectangle, consisting of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e rows and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e columns. We enumerate the rows of the rectangle from top to bottom with numbers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, and the columns — from left to right with numbers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e. Let\u0027s denote the cell at the intersection of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e-th row and the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e-th column as \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eInitially the pig stands in cell \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e, and in the end she wants to be in cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e. Since the pig is in a hurry to get home, she can go from cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e, only to either cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e + 1, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e + 1)\u003c/span\u003e. She cannot leave the forest.\u003c/p\u003e\u003cp\u003eThe forest, where the pig is, is very unusual. Some cells of the forest similar to each other, and some look very different. Peppa enjoys taking pictures and at every step she takes a picture of the cell where she is now. The path through the forest is considered to be \u003cspan class\u003d\"tex-font-style-it\"\u003ebeautiful\u003c/span\u003e if photographs taken on her way, can be viewed in both forward and in reverse order, showing the same sequence of photos. More formally, the line formed by the cells in order of visiting should be a \u003cspan class\u003d\"tex-font-style-it\"\u003epalindrome\u003c/span\u003e (you can read a formal definition of a palindrome in the previous problem).\u003c/p\u003e\u003cp\u003eCount the number of beautiful 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. Since this number can be very large, determine the remainder after dividing it by \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\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\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 500\u003c/span\u003e) — the height and width of the field.\u003c/p\u003e\u003cp\u003eEach 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 lowercase English letters identifying the types of cells of the forest. Identical cells are represented by identical letters, different cells are represented by different letters.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer — the number of beautiful paths modulo \u003cspan class\u003d\"tex-span\"\u003e10\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\u003e3 4\naaab\nbaaa\nabba\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003ePicture illustrating possibilities for the sample test. \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/98fbf6dcc80e154d30d3528c881392ba?v\u003d1714372759\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d4f2ca611a40922dfec105b4a3f0c584?v\u003d1714372759\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/e348a98f6f802abb18772cb17a9a2264?v\u003d1714372759\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/p\u003e\u003c/center\u003e"}}]}