Cho số tự nhiên ~N~ có không quá ~10^5~ chữ số. Một thao tác biến đổi là xóa một đoạn chữ số liên tiếp nhưng không được xóa hết số. Hai đoạn xóa khác vị trí được tính là hai cách khác nhau. Giữ nguyên ~N~ cũng được tính là một cách biến đổi.

Hãy đếm số cách biến đổi sao cho số thu được chia hết cho 3.

Subtask

• 100% số điểm: không có ràng buộc bổ sung ngoài các giới hạn đã nêu ở phần Input.

Ví dụ 1

2001

4

Ví dụ 2

160300

5