ĐẾM ĐƯỜNG ĐI ĐỐI XỨNG

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một ma trận A kích thước N×N(1N500). Các hàng đánh số từ 1 đến N từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái qua phải. Ô nằm trên hàng i, cột j gọi là ô Ai,j có giá trị là các chữ cái latin in hoa. Xét các đường đi từ ô (1;1) đến ô (N;N) mà trong một bước đi bạn chỉ được phép di chuyển xuống dưới hoặc qua phải. Mỗi đường đi được đại diện bởi một xâu được tạo thành bằng cách viết liên tiếp các kí tự trên đường đi. Hãy đếm số lượng đường đi có xâu đại diện là xâu đối xứng.

Input

  • Dòng đầu tiên là số nguyên N là kích thước của ma trận.
  • N dòng tiếp theo mỗi dòng gồm một xâu đại diện cho hàng thứ i của ma trận.

Output

  • Gồm một dòng duy nhất là số lượng đường đi có xâu đại diện là xâu đối xứng sau khi chia lấy dư cho 109+7.

Example

Input

Copy
4
ABCD
BXZX
CDXB
WCBA

Output

Copy
12

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.