题目描述

已知一个只由数字组成的字符串S,
请寻找S的子串,使得该子串以10进制数看待时,是2019的倍数.

输入

一行,字符串S

输出

一个整数,满足条件的子串个数.

样例1

输入

181712114

输出

2

样例2

输入

2019121141332019

输出

8

数据范围

30%:|S|≤8
60%:|S|≤10000
100%:|S|≤200000