Contest Edu #1 - Copy

View as PDF

Submit solution

Points: 0.50
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.