Đường đi đối xứng trên lưới

Cho một lưới chữ nhật gồm $n$ hàng và $m$ cột, mỗi ô được điền một chữ cái tiếng Anh thường. Hàng được đánh số từ $1$ tới $n$ từ trên xuống, cột được đánh số từ $1$ tới $m$ từ trái sang phải. Ô ở giao của hàng $r$ và cột $c$ được ký hiệu là $(r,c)$.

Bạn xuất phát từ ô $(1,1)$ và muốn đi đến ô $(n,m)$. Tại mỗi bước, từ ô $(r,c)$ bạn chỉ được di chuyển sang ô $(r+1,c)$ hoặc $(r,c+1)$ (không được ra ngoài lưới).

Một đường đi được gọi là đẹp nếu dãy chữ cái thu được khi ghi lại nhãn của các ô đi qua (kể cả ô đầu và ô cuối) tạo thành một xâu đối xứng (palindrome) — tức là đọc xuôi và đọc ngược cho cùng một xâu.

Hãy đếm số đường đi đẹp từ $(1,1)$ đến $(n,m)$. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, mỗi dòng chứa một xâu độ dài $m$ gồm các chữ cái tiếng Anh thường, mô tả lưới.

Dữ liệu ra

• In ra một số nguyên duy nhất là số đường đi đẹp modulo ${10}^9+7$.

Ràng buộc

• $1\le n,m\le 500$.

Ví dụ