Nhiệm vụ của bạn là tính toán số lượng xâu độ dài \(n\) có một từ khóa độ dài \(m\) được cho xuất hiện như xâu con của chúng. Tất cả các xâu bao gồm các kí tự A-Z.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): độ dài của xâu đáp án
• Dòng thứ hai có từ khóa độ dài \(m\)

Constraints

• \(1 \leq n \leq 1000\)
• \(1 \leq m \leq 100\)

Output

• In số lượng xâu chia lấy dư cho \(10^9 + 7\)

Example

6
ABCDB

52