Hôm nay là ngày Tuấn bắt đầu học các thuật toán cơ bản về xâu ở trên lớp và được giao bài tập về nhà. Tuấn giải những bài đầu rất nhanh nhưng đến bài cuối cậu đã gặp phải một bài tập khá hóc búa, nghĩ mãi không ra. Cho một xâu ~S~ có độ dài ~m~ và một số nguyên dương ~n~ ~(m \le n \le 5000)~.

Từ xâu ~S~, ta có thể tạo ra xâu mới theo quy tắc sau: thêm xâu ~T~ là tiền tố của ~S~ vào cuối xâu ~S~.

Ví dụ: Với xâu ~S = \texttt{baacb}~, các xâu có thể tạo ra có độ dài ~n = 8~ là ~\texttt{"baacbbbb", "baacbbba", "baacbbab", "baacbbaa"}~.

Đếm số xâu phân biệt độ dài ~n~ có thể tạo ra, in ra kết quả là phần dư khi chia cho ~10^9 + 7~.

Tuấn đang vô cùng bất lực khi đã dành hàng giờ để suy nghĩ nhưng vẫn chưa có ý tưởng gì. Bạn hãy giúp Tuấn giải bài tập trên nhé!

Input

• Dòng thứ nhất gồm 2 số nguyên dương ~m~ và ~n~ (~m \le n \le 5000~).

• Dòng thứ hai gồm một xâu ~S~ có độ dài ~m~.

Output

• Một số nguyên duy nhất là kết quả tìm được

Sample Input 1

5 8
baacb

Sample Output 1

4

Notes

Với xâu ~S = baacb~, các xâu có thể tạo ra có độ dài ~n = 8~ là:

• baacbbbb

• baacbbba

• baacbbab

• baacbbaa