Trong giờ tin học, Tý được học về hash xâu. Hash của một xâu được tính bằng công thức:

\[H(S) = (S[0] \cdot B^{n-1} + S[1] \cdot B^{n-2} + \cdots + S[n-1] \cdot B^{0}) \mod M\]

với \(B = 31\), \(M = 10^9 + 7\) và \(S[i]\) là mã số của ký tự thứ \(i\) (với a = 1, b = 2, ..., z = 26).

Hãy giúp Tý tính hash của xâu \(S\).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) chỉ gồm chữ cái in thường, độ dài không quá \(10^5\).

Định dạng đầu ra

• In ra một số nguyên là giá trị hash của xâu \(S\).

Ví dụ

Input:

abc

Output:

1026

Giải thích: hash = 1·31^2 + 2·31 + 3 = 961 + 62 + 3 = 1026.

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).