Người ta thực hiện mã hóa một xâu \(S\) gồm các chữ cái latin thường được đánh số từ \(1\) đến \(N\) với mã giả sau:

\(Hash = 0;\)

\(for\ i = 1\ \rightarrow N:\ Hash = Hash\ *\ 31\ +\ (S_i\ -\ 'a'\ +\ 1);\)

Con số \(31\) được chọn giống nhữ việc mình xem xâu \(S\) như là một số theo hệ cơ số \(31.\)

Tuy nhiên thì việc tạo ra một mã Hash với một xâu \(S\) có độ dài lớn sẽ dẫn đến việc tràn số (kể cả có long long) nên người ta sẽ tạo ra một mã Hash theo modun \(Mod.\)

Yêu cầu

Bạn hãy đưa ra mxa Hash của một xâu theo modun \(Mod\) với xâu \(S\) và giá trị \(Mod\) cho trước, hay nói cách khác, hãy in ra \(Hash\ \% Mod (C++).\)

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương \(Mod\ (Mod \leq 10^9).\)
• Dòng thứ hai gồm một xâu \(S\ (|S| \leq 10^4).\)

Kết quả

In ra mã Hash tương ứng.

Ví dụ