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.

Bộ test gồm 50 testcase, có test biên, test subtask nhỏ và test sát giới hạn.

Subtask

• 75% s? ?i?m: ~|N| \le 10^4~.
• 25% s? ?i?m: ~|N| \le 10^5~.