Bài 29: Hộp quà may mắn

Yêu cầu: 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ã số cần tìm là số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt. Số đặc biệt là số thỏa mãn đồng thời 2 điều kiện:

1. Chia hết cho 97.
2. Tổng các chữ số chia hết cho 3. (Chấp nhận các số có chữ số 0 đứng đầu).

Em hãy viết chương trình đưa ra mã số của hộp quà may mắn.

Dữ liệu vào (LUCKY.INP):

• Gồm một dòng là xâu ký tự ~S~ có độ dài ~|S| \le 10^5~.

Kết quả (LUCKY.OUT):

• Ghi ra một dòng ghi số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt.

Ví dụ:

Input:

2910

Output:

3

(Giải thích: Có 3 số đặc biệt thỏa mãn là 291, 2910 và 0).

Giới hạn (Subtasks):

• 50% số test ứng với độ dài xâu ~|S| \le 300~
• 30% số test ứng với độ dài xâu ~|S| \le 10^3~
• 20% số test ứng với độ dài xâu ~|S| \le 10^5~