Bài kiểm tra hôm nay của Per có một bài toán như sau.

Cho trước một xâu ~s~ và số nguyên ~k~. Một xâu Strix là xâu được tạo ra từ ~s~ bằng cách thực hiện đúng ~k~ lần thao tác: chèn một kí tự bất kỳ trong khoảng từ a đến z vào một vị trí bất kỳ của xâu hiện tại.

Hãy đếm số xâu Strix khác nhau có thể tạo ra.

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~k~ — số thao tác chèn kí tự.
• Dòng thứ hai chứa xâu ~s~ chỉ gồm các chữ cái in thường.

Kết quả

In ra số xâu Strix khác nhau, đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

1
j

Đầu ra:

51

Đầu vào:

2
baytachuyengiahoipen

Đầu ra:

144926

Giải thích: Ở ví dụ đầu tiên, chèn một kí tự vào bên trái j cho ~26~ xâu aj, bj, ..., zj; chèn vào bên phải cho ~26~ xâu ja, jb, ..., jz. Xâu jj xuất hiện ở cả hai cách nên chỉ đếm một lần, tổng cộng ~51~ xâu khác nhau.

Giới hạn

• ~1 \le k \le 10^6~
• ~1 \le |s| \le 10^6~

Đếm trực tiếp là bất khả thi, và trừ trùng lặp bằng tay cũng rất khó vì cùng một xâu có thể sinh ra theo nhiều cách khác nhau (như jj ở ví dụ trên).

Hãy đổi cách nhìn: các xâu Strix chính là các xâu ~t~ có độ dài ~n + k~ mà ~s~ là dãy con của ~t~ (với ~n = |s|~). Mỗi xâu như vậy đếm đúng một lần, không còn trùng lặp.

Đếm theo phép nhúng trái nhất của ~s~ vào ~t~ cho công thức

~\displaystyle\sum_{i=0}^{k} \dbinom{n + k}{i} \cdot 25^{i}~

trong đó ~i~ là số kí tự "tự do" không thuộc phép nhúng: mỗi kí tự đó chỉ có ~25~ lựa chọn vì nếu trùng với kí tự cần khớp tiếp theo thì phép nhúng trái nhất đã dùng nó rồi.

Đáng chú ý là đáp án không phụ thuộc vào nội dung của ~s~, chỉ phụ thuộc vào ~|s|~ và ~k~. Hãy tính trước bảng giai thừa đến ~n + k \le 2 \cdot 10^6~.