Cho số tự nhiên \(N\). Bằng cách giữ nguyên hoặc xóa đi một số chữ số liên tiếp của \(N\) (nhưng không xóa hết) ta nhận được một số mới, nếu số \(N\) được chia thành 2 phần thì số mới được ghép từ 2 phần này và giữ nguyên thứ tự.

Yêu cầu

• Hãy xác định tất cả các cách xóa như trên để số \(N\) mới sau khi xóa chia hết cho 3. Lưu ý: là 2 vị trí khác nhau sẽ tạo ra 2 cách xóa khác nhau. Số \(N\) giữ nguyên được coi là một cách xóa.

Dữ liệu vào

• Chứa số nguyên \(N\) (không quá \(10^5\) chữ số)

Dữ liệu ra

• Một số nguyên là số cách xóa tìm được

Ví dụ

Subtask:

• Subtask 1: \((50% số test)\) \(n \leq 300\)
• Subtask 2: \((25% số test)\) $ \(n \leq 10^4\)
• Subtask 2: \((25% số test)\) $ \(n \leq 10^5\)