Dấu Vân Tay Của Xâu

Với mỗi chữ cái thường, đặt $\mathrm{value}(a)=1,\mathrm{value}(b)=2,\dots ,\mathrm{value}(z)=26$. Cho xâu $s$ có độ dài $n$, dấu vân tay của xâu được định nghĩa bởi

Chỉ số ký tự bắt đầu từ $0$. Hãy tính $H(s)$.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa xâu $s$ gồm đúng $n$ chữ cái thường.

Output

• In giá trị $H(s)$ sau khi lấy phần dư theo $1.234567891\cdot 10^9$.

Constraints

• $1\le n\le 50$.
• Mỗi ký tự của $s$ thuộc từ $a$ đến $z$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 5$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
abcde

4739715