Chọn ĐTQG Quảng Trị 2026 - Bài 4 : Khóa số

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 trên 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 và đưa thông tin lên 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 \(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ìm khóa số \(T\) tương ứng với xâu \(S\).

Input

• 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 \le N \le 10^9\)).

Output

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

Example

mama 3

28

Scoring

• Subtask 1 (\(30\) điểm): Độ dài xâu \(S\) không vượt quá \(10^2\).
• Subtask 2 (\(30\) điểm): Độ dài xâu \(S\) không vượt quá \(10^3\).
• Subtask 3 (\(40\) điểm): Không có ràng buộc gì thêm.