J1 习题-11 相约2019

题目描述

某个咒语 $S$ 只包含 1 至 9等九个数字。 请找出里面的一些满足条件的状态： 从左到右，将第 $i$ 位到第 $j$ 位的数字截取出来，能否构成 2019 的倍数。

输入格式

一个字符串 $S$。

输出格式

输出一个整数，可行的截取方案数量。

样例输入1

1817181712114

样例输出1

3

样例1解析

方案1：截取字段位 $[1,5]$，拼成 18171； 方案2：截取字段位 $[5,9]$，拼成 18171； 方案3：截取字段位 $[9,13]$，拼成 12114。

样例输入2

14282668646

样例输出2

2

数据范围

对于 $100 \%$ 的数据：$1 \leq |S| \leq 2 \times 10^5$，保证字符串 $S$ 只包含数字 1-9。