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. Số đặc biệt là số chia hết cho 97 và có tổng các chữ số chia hết cho 3. Chấp nhận các số có chữ số 0 đứng đầu.

Yêu cầu: Đưa ra số lượng xâu con trong xâu ~S~ tạo thành số đặc biệt là mã số của hộp quà may mắn cần tìm.

Input

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

Output

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

Sample Input 1

2910

Sample Output 1

3

Giải thích: Có 3 số đặc biệt là 291, 2910, 0.

• 291: 291 chia hết cho 97, tổng chữ số 2+9+1=12 chia hết cho 3.
• 2910: 2910 chia hết cho 97, tổng chữ số 2+9+1+0=12 chia hết cho 3.
• 0: 0 chia hết cho 97, tổng chữ số 0 chia hết cho 3.

Giới hạn

• 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~.