Cho một lưới kích thước ~m*n~, mỗi ô chứa một ký tự chữ cái (viết thường hoặc viết hoa).

Bạn cần đếm số đường đi từ ô ~(1, 1)~ đến ô ~(m, n)~ sao cho mỗi bước chỉ được đi sang phải hoặc đi xuống.

Chuỗi ký tự tạo thành trên đường đi là một chuỗi Palindrome (đọc xuôi hay ngược đều giống nhau).

Yêu cầu: Tính số lượng đường đi từ ~(1, 1)~ đến ~(m, n)~ sao cho chuỗi ký tự thu được là palindrome. Kết quả có thể rất lớn, hãy in ra kết quả modulo 10⁹ + 7.

Input

• Dòng đầu chứa hai số nguyên ~m,n~ - kích thước của lưới.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ ký tự (không có khoảng trắng), biểu diễn các ký tự trong từng ô của lưới.

Output

Một số nguyên duy nhất - là số đường đi từ ~(1, 1)~ đến ~(m,n)~ tạo thành chuỗi palindrome, lấy mod ~10^9+7~.

Scoring

• Subtask 1 ~(30\%)~: ~m, n \leq 10~.
• Subtask 2 ~(70\%)~: ~m, n \leq 100~.

Example input 1

2 3
aba
aaa

Example output 1

1

Note 1

• Ba đường đi tạo thành palindrome là:
  • ~(1, 1)~ → ~(1, 2)~ → ~(1, 3)~ → ~(2, 3)~: abaa (không đối xứng).
  • ~(1, 1)~ → ~(2, 1)~ → ~(2, 2)~ → ~(2, 3)~: aaaa (đối xứng).

→ Có ~3~ đường hợp lệ.