解题思路

将原数字串 $S$ 看作由三部分组成：前缀 $A$（可为空）、被删除的非空连续子串 $B$、后缀 $C$（可为空）。删除 $B$ 后，剩余字符拼接成新的数字串，其数值等于 $V_A \times 10^{len_C} + V_C$，其中 $V_A$ 为 $A$ 的十进制数值，$len_C$ 为 $C$ 的长度，$V_C$ 为 $C$ 的数值。要求该值能被 $15$ 整除。

由于 $15$ 较小，可以采用模 $15$ 的前缀统计与后缀枚举，具体流程如下：

1. 预处理前缀模频数
   记 $L = |S|$。定义 pref[i][m] 为前 $i$ 个字符（$S[0..i-1]$）的所有前缀（包括空前缀）中，数值模 $15$ 等于 $m$ 的个数。
   初始时 pref[0][0] = 1（空前缀模 $15$ 为 $0$），其余为 $0$。

题目内容

在一个数字研究实验室里，工程师们需要对非常长的数字串进行精确裁剪。

给定一个仅由数字字符组成的字符串 $S$，你必须恰好删除一个非空连续子串，但不能删除整个字符串。删除后，剩余的字符将按原顺序拼接成一个新的数字串（允许存在前导零）。问有多少种不同的删除方案，使得最终得到的数字串所表示的整数恰好是 $15$ 的倍数。

两种方案不同，当且仅当所删除子串的起始位置或结束位置不同。注意，必须删除至少一个字符，且不能删除所有字符。

字符串 $S$ 的长度不超过 $10^5$。

输入描述

输入包含一行，为一个由数字组成的字符串 $S$，代表原始数字。字符串的长度 $L$ 满足 $1 \le L \le 10^5$。

输出描述

输出一个整数，表示满足条件的删除方案数。

样例1

输入

300

输出

4

说明

字符串长度为 3，所有可能的删除方案（非空连续子串且不能删除整个字符串）共 $5$ 种。

枚举每种删除方案，检查剩余数字串表示的整数是否为 15 的倍数：

• 删除第 1 个字符 3，剩余 "00"，值为 0，是 15 的倍数；
• 删除第 2 个字符 0，剩余 "30"，值为 30，是 15 的倍数；
• 删除第 3 个字符 0，剩余 "30"，值为 30，是 15 的倍数；
• 删除区间 [1,2] 的 "30"，剩余 "0"，值为 0，是 15 的倍数；
• 删除区间 [2,3] 的 "00"，剩余 "3"，值为 3，不是 15 的倍数。

共有 4 种方案满足条件。

样例2

输入

1515

输出

3

说明

字符串长度为 4，非空且非全串的删除区间共 $9$ 种。

逐一检查剩余数字模 15 的结果：

• 删除 [1,2] 的 "15"，剩 "15"，值为 15，是倍数；
• 删除 [2,3] 的 "51"，剩 "15"，值为 15，是倍数；
• 删除 [3,4] 的 "15"，剩 "15"，值为 15，是倍数；
• 删除单个字符 1、5、1、5 分别得到 "515" ($515 \\bmod 15 = 5$)、"115" ($115 \\bmod 15 = 10$)、"151" ($151 \\bmod 15 = 1$)、"151"，均不是倍数；
• 删除 [1,3] 剩 "5"，删除 [2,4] 剩 "1"，也都不是倍数。

共有 3 种方案满足条件。

样例3

输入

105

输出

1

说明

字符串长度为 3，合法的删除方案共 $5$ 种。

• 删除第 1 个字符 1 剩 "05"（值为 5），不是 15 的倍数；
• 删除第 2 个字符 0 剩 "15"（值为 15），是 15 的倍数；
• 删除第 3 个字符 5 剩 "10"（值为 10），不是倍数；
• 删除 [1,2] 的 "10" 剩 "5"，不是倍数；
• 删除 [2,3] 的 "05" 剩 "1"，不是倍数。

共有 1 种方案满足条件。

样例4

输入

0

输出

0

说明

字符串长度为 1，唯一的删除方案是删除整个字符串，此时剩余字符为空，不符合“不能删除所有字符”的规则。因此没有任何满足条件的删除方案，答案为 0。