Hộp quà may mắn

Trong một buổi ngoại khóa của Câu lạc bộ Tin học, giáo viên tổ chức trò chơi tìm "Hộp quà may mắn". Các đội chơi sẽ nhận được một xâu \(S\) chỉ gồm các ký tự số. Mỗi đội phải tìm được mã số của hộp quà may mắn.

Mã số cần tìm là số lượng xâu con trong xâu \(S\) tạo thành số đặc biệt. Một số được gọi là đặc biệt nếu số đó chia hết cho \(97\) và tổng các chữ số của nó chia hết cho \(3\). Chấp nhận các số có chữ số \(0\) đứng đầu.

Yêu cầu. Hãy tính số lượng xâu con trong xâu \(S\) tạo thành số đặc biệt.

Input

Một dòng chứa xâu ký tự số \(S\) (\(|S| \le 10^5\)).

Output

Ghi ra một số nguyên là số lượng xâu con trong xâu \(S\) tạo thành số đặc biệt.

Input

%
2910

Output

%
3

Notes

Ba xâu con thỏa mãn là 291, 2910 và 0.

Scoring

• (50%) \(|S| \le 300\).
• (30%) \(|S| \le 10^3\).
• (20%) \(|S| \le 10^5\).