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;

string s;
const int mod = 2019;
int n, ans;

int r[2019] = { 1 };

int main() {
	cin >> s;
	n = s.size();
	for (int i = 0, d = 1, m = 0; i < n; i++, d = d * 10 % mod) {
		m = (m + (s[n - 1 - i] - '0') * d) % mod;
		r[m]++;
	}
	for (int i = 0; i < mod; i++)
		ans += r[i] * (r[i] - 1) / 2;
	cout << ans << endl;

}
