Lưu ý: hiện tại bài đang lỗi không thể chấm bằng file .inp .out, nên các bạn không cần freopen mà chỉ cần nhập bằng màn hình và in ra màn hình thôi nhé

Chuyển đổi số là một xu thế tất yếu với hầu hết các công việc được thực hiện trong môi trường số. Cùng với sự phát triển nhanh chóng của AI, số người tham gia làm việc trong môi trường số ngày càng nhiều, song song với đó là nhu cầu nâng cao các giải pháp bảo mật thông tin và khóa số là một trong những giải pháp.

IT làm việc cho một công ty bảo mật và đã nghĩ ra giải pháp mã hóa các chuỗi mật khẩu thành các con số như sau: Từ một xâu S đã cho chỉ chứa các chữ cái tiếng Anh, IT liệt kê ra tất cả các xâu con khác rỗng của xâu S, sau đó gom các xâu con giống nhau vào cùng một cụm và đếm số lượng xâu trong mỗi cụm. Tiếp theo IT viết chương trình cho sinh ra một số ngẫu nhiên N và tính số T là tổng các lũy thừa bậc N của số lượng xâu của các cụm, T được gọi là khóa số của xâu S.

Ví dụ: N = 3 và xâu S là "mama" thì các xâu con khác rỗng của xâu S là: "m", "a", "m", "a", "ma", "am", "ma", "mam", "ama", "mama" được gom thành 7 cụm (cụm 1 chứa xâu "m" với số lượng là 2, cụm 2 chứa xâu "a" với số lượng là 2, cụm 3 chứa xâu "ma" với số lượng là 2, cụm 4 chứa xâu "am" với số lượng là 1, cụm 5 chứa xâu "mam" với số lượng là 1, cụm 6 chứa xâu "ama" với số lượng là 1, cụm 7 chứa xâu "mama" với số lượng là 1). Khi này tổng T = 2^3 + 2^3 + 2^3 + 1^3 + 1^3 + 1^3 + 1^3 = 28.

Yêu cầu

Bạn được cho một xâu S và số N, hãy lập trình tính khóa số T tương ứng với xâu S.

Dữ liệu

Cho trong tệp DKEY.INP gồm một dòng duy nhất chứa xâu ký tự S và số nguyên dương N cách nhau bởi một dấu cách (độ dài xâu S không vượt quá 10^4, 1 <= N <= 10^9).

Kết quả

Ghi ra tệp DKEY.OUT một số nguyên duy nhất là phần dư của phép chia T cho 10^9 + 7.

Ví dụ

Input

mama 3

Output

28

Ràng buộc

• Subtask 1: 30% số tests tương ứng 30% số điểm có độ dài xâu S không vượt quá 10^2.
• Subtask 2: 30% số tests tương ứng 30% số điểm có độ dài xâu S không vượt quá 10^3.
• Subtask 3: 40% số điểm không có ràng buộc gì thêm.