Có bao nhiêu xâu có thể được tạo thành bằng cách áp dụng thao tác sau trên một xâu \(S\) cho trước đúng \(K\) lần: "chọn một ký tự in thường trong bảng chữ cái tiếng Anh và chèn vào bất cứ đâu trong xâu \(S\)"?

Đáp án có thể rất lớn, nên hãy in kết quả chia lấy dư cho \((10^9+7)\).

Input

• Dòng đầu tiên chứa một số nguyên \(K\) \((1 \leq K \leq 10^6)\).
• Dòng thứ hai chứa một xâu \(S\) có độ dài dương không quá \(10^6\), chỉ gồm các ký tự trong bảng chữ cái tiếng Anh.

Output

• In ra số lượng xâu thỏa mãn đề bài, chia lấy dư cho \((10^9+7)\).

Example

5
oof

575111451

37564
whydidyoudesertme

318008117

Constraints

• \(1 \leq K \leq 10^6\)
• \(1 \leq |S| \leq 10^6\)
• \(S\) chỉ gồm các ký tự tiếng Anh in thường.