Cho một xâu ~X~ có độ dài xâu không quá ~10^4~, chỉ gồm các kí tự tiếng Anh in hoa. Viết liên tiếp ~K~ lần xâu ~X~ được xâu ~S~. Hỏi có bao nhiêu xâu HN được tạo ra bằng cách xoá các kí tự từ xâu ~S~.

Dữ liệu vào từ tệp văn bản: DEMHN.INP

• Dòng đầu tiên chứa xâu ~X~;
• Dòng thứ hai chứa một số nguyên dương ~K~ (~K \leq 10^9~).

Kết quả ghi ra tệp văn bản: DEMHN.OUT

• In ra kết quả của bài toán sau khi chia lấy dư cho ~10^9 + 7~.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~K = 1~;
• Subtask 2 (~20\%~ số điểm): ~K \leq 10^3~;
• Subtask 3 (~20\%~ số điểm): ~K \leq 10^6~;
• Subtask 4 (~10\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

HNNH
2

Sample Output

8

Giải thích

• Xâu ~S~ có dạng HNNHHNNH.
• Các bộ vị trí tạo thành xâu HN thỏa mãn là ~(1, 2), (1, 3), (1, 6), (1, 7), (4, 6), (4, 7), (5, 6), (5, 7)~.