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;

const int N=2e5+20;

int n,mod=2019,m[N];
long long dp[N],p[N],ans;
char a[N];

int main()
{
	scanf(" %s",a+1);
	n=strlen(a+1);

	p[0]=1;
	for(int i=1;i<=n;i++)
	{
		p[i]=(p[i-1]*10)%mod;
		dp[i]=(dp[i-1]*10+a[i]-'0')%mod;
	}

	for(int i=n;i>=1;i--)
	{
		dp[i]=(dp[i]*p[n-i])%mod;
		m[dp[i]]++;
		ans+=m[dp[i]]-1;
	}

	printf("%lld",ans+m[0]);
}