Nhập vào xâu ký tự \(S\) gồm các chữ cái tiếng anh viết thường (lowercase English letters). Hãy đếm xem có bao nhiêu xâu khác nhau có thể tạo ra bằng cách chèn \(k\) chữ cái tiếng anh viết thường vào xâu \(S\). Chú ý, thứ tự của các chữ cái ban đầu của \(S\) không được thay đổi. Các chữ cái được chèn thêm có thể nằm giữa, đầu, hoặc cuối các chữ cái của xâu \(S\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Dòng thứ nhất chứa số nguyên dương \(K\);
• Dòng thứ hai chứa xâu ký tự \(S\).

Output

• In ra số dư của kết quả khi cho cho \(10^9+7\).

Ví dụ

Sample input 1

5
aab

Sample output 1

575111451

Ví dụ một số xâu có thể tạo ra: vwxyzaab, mnapqarb, aaghibjk, aabaabab

Sample input 2

180320
bruteforce

Sample output 2

796476410

Ràng buộc

• \(1\leq k\leq10^6\);
• \(1\leq |S|\leq10^6\).