KhaiTCL và Theanhto là đôi bạn thân. Một ngày nọ, cả hai cùng học được tính chất khá là hay ho của một chuỗi đối xứng đó là khi đảo ngược lại tất cả các kí tự thì nó cũng tạo thành một chuỗi bằng với chuỗi ban đầu. Sau đó, KhaiTCL chọn một số nguyên \(k\) và đố Theanhto đếm được số lượng xâu đối xứng độ dài \(k\) chỉ gồm các ký tự Latinh in thường (a \(\rightarrow\) z).

Điều này quả thực quá dễ đối với Theanhto, cậu ấy đã tính toán rất nhanh chỉ trong vòng một nốt nhạc. Các bạn có thể nghĩ xem kết quả ở đây là gì? Tuy nhiên, để tăng độ khó cho việc tính toán, KhaiTCL lại sinh ra \(n\) xâu \(s_1,s_2,\ldots,s_n\) và mỗi xâu cũng chỉ gồm các ký tự Latinh in thường. Lúc này KhaiTCL muốn Theanhto tính xem có bao nhiêu xâu đối xứng mà ít nhất \(1\) trong \(n\) xâu \(s_1,s_2,\ldots,s_n\) này xuất hiện trong xâu đối xứng đó ít nhất \(1\) lần. KhaiTCL định nghĩa xâu \(a\) xuất hiện trong xâu \(b\) nếu tồn tại vị trí \(i \in [1,|b|-|a|+1]\) mà \(a_j = b_{i+j-1} \ \forall j \in [1,|a|]\), ở đây mỗi xâu có các kí tự được đánh chỉ số từ \(1\) từ trái qua phải và \(|t|\) là độ dài của xâu \(t\) nào đó.

Do KhaiTCL thấy hơi hụt hẫng khi Theanhto giải được bài tập đầu tiên quá nhanh nên cậu mới nghĩ ra bài toán thứ hai nhưng thật không may khi bài toán này chính cậu cũng không biết phải đếm như thế nào kể cả khi cậu có một cái máy tính trong tay để lập trình. Thông qua cuộc thi LQDOJ CUP, KhaiTCL quyết định tìm đến những lập trình viên giỏi nhất nhằm giúp KhaiTCL giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 10 ^ 3\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_i\) (\(1 \leq |s_i| \leq 10 ^ 3\)).
• Tổng độ dài các xâu \(s_i\) không vượt quá \(10 ^ 3\).

Output

• Một dòng duy nhất chứa một số nguyên là phần dư của kết quả bài toán khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|s_1| = |s_2| = \ldots = |s_n| = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n = 1\) và \(|s_1| = 2\).
• Subtask \(3\) (\(20\%\) số điểm): \(n=1\).
• Subtask \(4\) (\(20\%\) số điểm): \(|s_i| \leq 20 \ \forall i \in [1, n]\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

2 3
a
aa

51