三倍子串

题目描述:

给定一个十进制正整数n，请问可以从n中截取多少种不同的子串，使得子串构成的数字是3的倍数。

例如，当n = 1234 时，有且仅有3，12，123， 234这四个子串是3的倍数。

输入格式:

单个整数，表示输入的数字n。

输出格式:

单个整数，表示3的倍数的子串的数量。

样例输入:

95764

样例输出:

6

提示:

对于 60 % 的数据， 1 ≤ n ≤ 10¹⁰⁰⁰

对于 80 % 的数据， 1 ≤ n ≤ 10¹⁰⁰⁰⁰

对于 100 % 的数据， 1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰

时间限制: 1000ms
空间限制: 256MB

---