三倍子串(Triple Substring)

题目描述

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

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

输入格式

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

输出格式

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

样例输入 #1

95764

样例输出 #1

6

样例说明 #1

子串 6、9、57、576、957、9576 是 3 的倍数。

样例输入 #2

1111

样例输出 #2

2

样例说明 #2

有两个 111 都是 3 的倍数。

数据范围

• 对于 20% 的数据，$1 \le n \le 10^9$；
• 对于 50% 的数据，$1 \le n \le 10^{100}$；
• 对于 70% 的数据，$1 \le n \le 10^{1000}$；
• 对于 100% 的数据，$1 \le n \le 10^{100000}$。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布