Tổng giá trị xâu con

Ta định nghĩa giá trị của một xâu \(s\) gồm các chữ cái thường tiếng Anh như sau: mỗi ký tự \(s_i\) đóng góp \(i^2 \times v(s_i)\) vào giá trị, trong đó \(i\) là vị trí của ký tự trong xâu (đánh số từ \(1\)) và \(v(s_i)\) là thứ tự của chữ cái đó trong bảng chữ cái (\(v(\texttt{a}) = 1\), \(v(\texttt{b}) = 2\), ..., \(v(\texttt{z}) = 26\)). Giá trị của \(s\) là tổng các đóng góp này.

Ví dụ: xâu bca có giá trị \(1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 1 = 2 + 12 + 9 = 23\).

Cho xâu \(t\). Hãy tính tổng giá trị của mọi xâu con liên tiếp của \(t\) (mỗi cặp vị trí đầu - cuối khác nhau được tính là một xâu con riêng, kể cả khi nội dung trùng nhau). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\).

Input

Một dòng duy nhất chứa xâu \(t\).

Output

In ra một số nguyên là tổng giá trị các xâu con của \(t\), lấy phần dư khi chia cho \(10^9 + 7\).

Constraints

• \(t\) chỉ gồm các chữ cái thường a-z.
• \(1 \le |t| \le 2 \times 10^5\)

Sample Input 1

bca

Sample Output 1

50

Explanation

• Xâu con độ dài \(1\): b, c, a có giá trị lần lượt \(2, 3, 1\).
• Xâu con độ dài \(2\): bc có giá trị \(2 + 4 \cdot 3 = 14\); ca có giá trị \(3 + 4 \cdot 1 = 7\).
• Xâu con độ dài \(3\): bca có giá trị \(23\).

Tổng: \(2 + 3 + 1 + 14 + 7 + 23 = 50\).