题目描述

小 A 得到一个只包含数字字符的字符串 $s$。对于 $s$ 的一个连续区间，如果它同时满足以下三个条件，则称它为合格区间：区间长度至少为 $2$；区间的第一个字符与最后一个字符相同；区间内所有数字之和能被 $3$ 整除。请计算合格区间的数量。

输入格式

输入一行，包含一个字符串 $s$，仅由字符 0 到 9 组成。

输出格式

输出一个整数，表示合格区间的数量。

样例

30303

4

样例解释

合格区间共有 $4$ 个，分别是位置 $1$ 到 $3$、$1$ 到 $5$、$2$ 到 $4$、$3$ 到 $5$ 对应的区间。

数据范围

$1 \le |s| \le 2000$。

由于区间数量可能较多，建议使用 long long 保存答案。