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;
typedef long long ll;
int main(){
  string s; cin >>s; int n=s.size(),x=1,ans=0;
  vector<int>v(n+1,0); vector<int>r(2019,0);
  for(int i=1; i<=n; i++){
    v[i]=(v[i-1]+x*(s[n-i]-'0'))%2019;
    x=(x*10)%2019; r[v[i]]++;
  }
  for(int i=0; i<2019; i++) ans+=r[i]*(r[i]-1)/2;
  cout <<ans+r[0];
return 0;}