{"code":"palpath","name":"Xâu đường đi đối xứng","description":"Cho lưới ô vuông kích thước $n$ x $n$, các hàng đánh số $1…n$ từ trên xuống dưới, các cột đánh số $1…n$ từ trái sang phải. Mỗi ô trong lưới chứa một kí tự chữ cái latin in hoa. Xét các đường đi từ ô $(1;1)$ đến ô $(n;n)$ chỉ đi từ một ô sang ô kề cạnh bên phải hoặc bên dưới. Mỗi đường đi được đại diện bởi một xâu kí tự là dãy các kí tự trong các ô trên đường đi dọc theo hành trình. Đếm số đường đi có xâu đại diện là xâu đối xứng.\r\n\r\n#### Input \r\n* Dòng 1: số nguyên $n$ $(1 \\leq n \\leq 500)$. \r\n* Dòng 2…$n+1$: dòng $i+1$ chứa một xâu độ dài $n$ mô tả hàng $i$ của lưới.\r\n\r\n#### Output\r\n * Dòng 1:  số nguyên là số lượng đường đi có xâu đại diện là xâu đối xứng, lấy phần dư khi chia cho $(10^9+7)$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4\r\n        ABCD\r\n        BXZX\r\n        CDXB\r\n        WCBA\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        12\r\n        ```\r\n    ??? warning \"Note\"\r\n        * Xâu ABCDCBA là đại diện của 1 đường\r\n        * Xâu ABCWCBA là đại diện của 1 đường\r\n        * Xâu ABXZXBA là đại diện của 6 đường\r\n        * Xâu ABXDXBA là đại diện của 4 đường","points":1000.0,"partial":false,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}