Given is a string S consisting of digits from `1` through `9`.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

* 1 ≤ |S| ≤ 200000
* S is a string consisting of digits from `1` through `9`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Examples

Input

1817181712114


Output

3


Input

14282668646


Output

2


Input

2119


Output

0
#include <bits/stdc++.h>
using namespace std;

int main() {
	long n,m,i,j,k,ans,cur,res;
	string s;
	cin >> s;
	vector<long> dp1(2019,0),dp2(2019,0),dp0(2019,0);
	
	long c;
	ans=0;
	for(i=0; i<s.size(); i++){
		c=s[i]-'0';
		for(j=0; j<2019; j++){
			dp2[(10*j)%2019]=dp1[j];
		}
		for(j=0; j<2019; j++){
			dp1[(j+c)%2019]=dp2[j];
		}
		dp1[c]++;
		ans+=dp1[0];
	}
	
	cout << ans;
	return 0;
}