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} + \dots + S[n-1] \cdot B^0) \bmod 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\).