MofK vừa được tặng một món quà là một tấm bảng gồm ~m~ dòng và ~n~ cột, mỗi ô của bảng chứa một chữ cái.
Với tấm bảng vừa nhận được MofK liền nghĩ ra một trò chơi như sau, MofK sẽ xuất phát từ ô ~(1,\ 1)~ và đi đến ô ~(m,\ n)~, ở mỗi bước đi chỉ được đi sang phải hoặc xuống dưới so với ô MofK đang đứng. Khi đi qua mỗi ô MofK ghi lại chữ cái của ô đó để tạo thành một xâu ~s~ gồm ~m + n - 1~ kí tự khi đi đến ô ~(m,\ n)~.
Vì rất yêu thích món quà được tặng nên MofK quyết định sẽ thử mọi cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ và tạo ra tất cả các xâu có thể. Cuối cùng MofK nghĩ ra một công thức tính điểm như sau: với mỗi xâu ~s~, nếu có ~f(s)~ cách đi để tạo thành xâu ~s~ thì MofK sẽ được ~f(s)^2~ điểm.
Vì số lượng cách đi cũng như số lượng xâu tạo ra quá lớn khiến cho MofK không thể tự mình tính toán số điểm theo như công thức mà mình đã đề ra. Bạn hãy giúp MofK tính số điểm của mình nhé.
Input
Dòng đầu nhập hai số nguyên ~m~ và ~n~ ~(m \times n \leq 10^5)~ tương ứng là số hàng và cột của bảng.
~m~ dòng tiếp theo mỗi dòng nhập một xâu gồm ~n~ kí tự miêu tả một hàng trong bảng.
Output
Một số nguyên duy nhất là số điểm mà MofK nhận được (modulo ~10^9 + 7~).
Scoring
Subtask 1 (~30\%~): ~m,n \le 10~
Subtask 2 (~30\%~): ~m\times n \le 5000~
Subtask 3 (~40\%~): Không có điều kiện gì thêm
Sample Input 1
3 4
aaaa
aaab
abaa
Sample Output 1
34
Notes
Trong test ví dụ, Khi thử tất cả cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ sẽ tạo ra các xâu sau:
~3~ xâu aaaaaa
~4~ xâu aaaaba
~3~ xâu aaabaa
Số điểm nhận được là ~3^2 + 4^2 + 3^2 = 34~
Bình luận