Nhập vào một xâu thập phân, bạn hãy đếm số cách tách ra một xâu con của $S$ có giá trị chia hết cho $9$.

Ghi chú 1: Xâu thập phân là xâu chỉ chứa các kí tự số từ $0$ tới $9$. Giá trị của một xâu thập phân là giá trị trong hệ thập phân mà nó biểu diễn.

Ví dụ: Xâu "0023" có giá trị $23$, xâu "0000" có giá trị $0$.

Ghi chú 2: Xâu con của một xâu $S$ là chuỗi các kí tự liên tiếp trong $S$.

Ví dụ: "1234", "4ab", ... là các xâu con của xâu "11234abc".

Đầu vào

Một xâu thập phân duy nhất độ dài không quá ${10}^6$.

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán, do kết quả có thể rất lớn bạn hãy lấy phần dư khi chia cho số ${10}^9+7$.

Subtask

$30\mathrm{\%}$ số test xâu thập phân độ dài không quá $100$.

$30\mathrm{\%}$ số test xâu thập phân độ dài không quá $1000$.

Ví dụ

Đầu vào:

00108

Đầu ra:

7

Giải thích: Nếu xâu $00108$ bắt đầu từ chỉ số $0$, các đoạn xâu con $[0,0],[1,1],[0,1],[3,3],[0,4],[1,4],[2,4]$ tách ra có giá trị chia hết cho $9$