{"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 đang đi dạo và đi vào rừng. Thật là một sự trùng hợp kỳ lạ! Rừng có hình dạng của một hình chữ nhật, bao gồm \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e hàng và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e cột. Chúng ta đánh số các hàng của hình chữ nhật từ trên xuống dưới với các số từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, và các cột — từ trái sang phải với các số từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e. Hãy ký hiệu ô tại giao điểm của hàng thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e và cột thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e là \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eBan đầu, con heo đứng ở ô \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e, và cuối cùng cô ấy muốn ở ô \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e. Vì con heo đang vội về nhà, cô ấy có thể đi từ ô \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e, chỉ đến ô \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e + 1, \u003ci\u003ec\u003c/i\u003e)\u003c/span\u003e hoặc \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e + 1)\u003c/span\u003e. Cô ấy không thể rời khỏi rừng.\u003c/p\u003e\u003cp\u003eRừng, nơi con heo đang ở, rất không bình thường. Một số ô của rừng giống nhau, và một số trông rất khác nhau. Peppa thích chụp ảnh và mỗi bước cô ấy đi, cô ấy chụp một bức ảnh của ô mà cô ấy đang ở. Con đường qua rừng được coi là \u003cspan class\u003d\"tex-font-style-it\"\u003eđẹp\u003c/span\u003e nếu các bức ảnh chụp trên đường đi của cô ấy, có thể được xem theo cả hai chiều, hiển thị cùng một chuỗi ảnh. Cụ thể hơn, dòng được tạo thành từ các ô theo thứ tự ghé thăm phải là một \u003cspan class\u003d\"tex-font-style-it\"\u003eđối xứng\u003c/span\u003e (bạn có thể đọc một định nghĩa chính thức về một đối xứng trong vấn đề trước).\u003c/p\u003e\u003cp\u003eĐếm số lượng con đường đẹp từ ô \u003cspan class\u003d\"tex-span\"\u003e(1, 1)\u003c/span\u003e đến ô \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e. Vì số lượng này có thể rất lớn, xác định phần dư sau khi chia cho \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên \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) — chiều cao và chiều rộng của lĩnh vực.\u003c/p\u003e\u003cp\u003eMỗi trong số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e dòng tiếp theo chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e chữ cái thường xác định loại ô của rừng. Các ô giống nhau được biểu diễn bằng các chữ cái giống nhau, các ô khác nhau được biểu diễn bằng các chữ cái khác nhau.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn một số nguyên duy nhất — số lượng con đường đẹp theo modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Ví dụ 1","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"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eHình minh họa các khả năng cho bài kiểm tra mẫu. \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/98fbf6dcc80e154d30d3528c881392ba?v\u003d1710062239\" 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\u003d1710062239\" 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\u003d1710062239\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/p\u003e\u003c/center\u003e"}}]}