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\).

Output

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

Constraints

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

Example

Note

Xâu đáp án sẽ có dạng ABCDB\(x\) hoặc \(x\)ABCDB trong đó \(x\) là bất kỳ ký tự nào giữa A-Z.