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\%\) số test xâu thập phân độ dài không quá \(100\).

\(30\%\) 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\)