Cho xâu ~S~ có độ dài ~n \ (n \leq 5000)~ chỉ gồm các chữ cái tiếng Anh in thường và một số nguyên dương ~m~.

Một xâu a có độ dài ~n_1 \ (n_1 \leq n)~ được gọi là xâu tiền tố của ~S~ nếu như a trùng với xâu được tạo bởi ~n_1~ ký tự đầu tiên của ~S~.

Từ xâu ~S~, ta có thể tạo được xâu mới bằng cách thêm tiền tố ~a~ của ~S~ vào cuối xâu ~S~, thao tác này có thể được thực hiện nhiều lần.

Yêu cầu

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

Dữ liệu

• Dòng thứ nhất gồm 2 số nguyên dương ~n~ và ~m \ (n \leq m \leq 5000)~.
• Dòng thứ hai gồm một xâu ~S~ có độ dài ~n~.

Kết quả

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Sample Input

5 8
baacb

Sample Output

4

Giải thích

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

• baacbbbb
• baacbbba
• baacbbab
• baacbbaa