题目内容

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

给定一个仅由数字字符组成的字符串 $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。