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.

Input

• Dòng 1: số nguyên \(n\) \((1 \leq n \leq 500)\).
• 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.

Output

• 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)\).

Example

4
ABCD
BXZX
CDXB
WCBA

12