stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):


#include<bits/stdc++.h>

using namespace std;



long long con=1000000007,a[100070],cnt[100070],fac[100050];



long long fact(long long n)

{

    if(n==0)

    {

        return 1;

    }

    long long mul=1,i;



    mul=fac[n-1]*n;

    mul=mul%con;



    return mul;

}



int main()

{



    long long n,i,ans=1;



    for(i=0; i<100050; i++)

    {

        fac[i]=fact(i);

    }

    scanf("%lld",&n);



    for(i=0; i<n; i++)

    {

        scanf("%lld",&a[i]);

        cnt[a[i]]++;

    }



    for(i=1;i<100050; i++)

    {

        if(cnt[i]%2!=0)

        {

            printf("0");

            return 0;

        }





        ans*=fac[cnt[i]];

        ans=ans%con;

    }



    printf("%lld",ans);

    return 0;

}




// Optimized solution to the same problem (faster):
// ====================================

//   author: M_sea

//   website: https://m-sea-blog.com/

// ====================================

#include <bits/stdc++.h>

#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)

#define debug(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

typedef long long ll;



int read() {

	int X=0,w=1; char c=getchar();

	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

	return X*w;

}



const int N=100000+10;

const int mod=1e9+7;

int qpow(int a,int b) { int c=1;

	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;

	return c;

}



int n,a[N];



int main() {

	n=read();

	for (int i=1;i<=n;++i) a[i]=read();

	sort(a+1,a+n+1);

	if (n&1) {

		int flag=(a[1]==0);

		for (int i=2;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	} else {

		int flag=1;

		for (int i=1;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iomanip>

#include <vector>

using namespace std;

const int maxn = 1e5+100;

const int MOD = 1e9+7;

const double Pi = 3.141592654;

typedef long long ll;

typedef unsigned long long ull;





int main()

{

    int n;

    cin >> n;

    int a[maxn];

    int vis[maxn];

    int st;

    ll ans = 1;

    memset(vis, 0, sizeof(vis));

    for(int i=1 ; i<=n ; ++i)

    {

        cin >> a[i];

        vis[a[i]] ++;

    }

    if(!(n%2))//even

    {

        if(vis[0])

        {

            cout << 0 << endl;

            return 0;

        }

        for(int i=1 ; i<=n ; i+=2)

        {

            ans = (ans%MOD)*2%MOD;

            if(vis[i] != 2)

        {

            cout << 0 << endl;

            return 0;

        }

        }

    }

    else

    {

        if(vis[0] != 1)

        {

            cout << 0 << endl;

            return 0;

        }

        for(int i=2 ; i<=n ; i+=2)

        {

            ans = (ans%MOD)*2%MOD;

            if(vis[i] != 2)

        {

            cout << 0 << endl;

            return 0;

        }

        }

    }

    cout << ans << endl;



}



//9(4(7(1)(2))(3(6)(8)))(5(10)(11(12)))


// Optimized solution to the same problem (faster):
// ====================================

//   author: M_sea

//   website: https://m-sea-blog.com/

// ====================================

#include <bits/stdc++.h>

#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)

#define debug(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

typedef long long ll;



int read() {

	int X=0,w=1; char c=getchar();

	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

	return X*w;

}



const int N=100000+10;

const int mod=1e9+7;

int qpow(int a,int b) { int c=1;

	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;

	return c;

}



int n,a[N];



int main() {

	n=read();

	for (int i=1;i<=n;++i) a[i]=read();

	sort(a+1,a+n+1);

	if (n&1) {

		int flag=(a[1]==0);

		for (int i=2;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	} else {

		int flag=1;

		for (int i=1;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



int main() {

	//cout<<"GfG!";

	long long int n, a[1000000], i, j, k, f = 1 ;

	unsigned long long int tot = 1, M = 1000000007;

	cin>>n;

	for (i = 0; i < n; i++)

	{

	    cin>>a[i]; 

	}

	sort(a, a + n);

	i = 0;  j = 0; 

	while (i < n)

	{

	    if (n == 1)

	    {   break;  }

	    else if (a[i] == 0 && a[i+1] != 0)

	    {

	        i++;   

	    }

	    else if (a[i] == 0 && a[i+1] == 0)

	    {       f = 0;  break;  }

	    else

	    {

	        if (i == n - 1)

	        {       f = 0;  break;  }

	        else if(a[i+1] == a[i] && (a[j+2] - a[j] == 2))

	        {

	            tot = (tot * 2) % M;

	            i += 2;   j += 2;   

	            if (j == n - 2)

	                j = 0;

	                

	        }

	        else

	        {

	            f = 0;  break;

	        }

	    }

	     

	}

	if (f)

	    cout<<tot;

	else

	    cout<<"0";

	return 0;

}


// Optimized solution to the same problem (faster):
// ====================================

//   author: M_sea

//   website: https://m-sea-blog.com/

// ====================================

#include <bits/stdc++.h>

#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)

#define debug(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

typedef long long ll;



int read() {

	int X=0,w=1; char c=getchar();

	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

	return X*w;

}



const int N=100000+10;

const int mod=1e9+7;

int qpow(int a,int b) { int c=1;

	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;

	return c;

}



int n,a[N];



int main() {

	n=read();

	for (int i=1;i<=n;++i) a[i]=read();

	sort(a+1,a+n+1);

	if (n&1) {

		int flag=(a[1]==0);

		for (int i=2;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	} else {

		int flag=1;

		for (int i=1;i<=n;i+=2)

			if (a[i]!=i||a[i+1]!=i) { flag=0; break; }

		if (flag) printf("%d\n",qpow(2,n/2));

		else puts("0");

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

    double a,b,c;

    cin>>a>>b>>c;

    c=min(c,b-1);

    cout<<floor(a*c/b)-a*floor(c/b)<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int main() {

    long long int x,ans, a, b,n;

    scanf("%lld %lld %lld",&a, &b, &n);



     x = min(n, b-1);

    ans = floor(a*x/b) - a * floor(x/b);

    printf("%lld\n", ans);



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cmath>

using namespace std;

#define ll long long

ll a,b,n;

ll x;

ll gg;

int main(){

	cin>>a>>b>>n;

	x=min(b-1,n);

	gg=a*x/b;

	cout<<gg<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int main() {

    long long int x,ans, a, b,n;

    scanf("%lld %lld %lld",&a, &b, &n);



     x = min(n, b-1);

    ans = floor(a*x/b) - a * floor(x/b);

    printf("%lld\n", ans);



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

    long int a,b,c;

    cin>>a>>b>>c;

    c=min(c,b-1);

    cout<<floor(a*c/b)<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int main() {

    long long int x,ans, a, b,n;

    scanf("%lld %lld %lld",&a, &b, &n);



     x = min(n, b-1);

    ans = floor(a*x/b) - a * floor(x/b);

    printf("%lld\n", ans);



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 2e5 + 100; 

const double pi = acos(-1.0);



inline ll read()

{

    ll kk=0,f=1;

    char cc=getchar();

    while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}

    while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}

    return kk*f;

}



ll floor(ll a,ll b);

int main(void)

{

	ll a,b,n;

	a=read();b=read();n=read();

	

	ll x=min(n,b-1);

	ll ans = floor(a*x/b) - a*floor(x/b); 

	printf("%lld",ans);

	return 0;

}



ll floor(ll a,ll b)

{

	ll c=a/b;

	return a/b;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int main() {

    long long int x,ans, a, b,n;

    scanf("%lld %lld %lld",&a, &b, &n);



     x = min(n, b-1);

    ans = floor(a*x/b) - a * floor(x/b);

    printf("%lld\n", ans);



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;

const int INF = 1e9;



ll a, b, n, c1, c2, ans = 0;



ll f(ll x) { return floor(a * x / b) - a * floor(x / b); }



ll g(ll x) {

  ll l = 0, r = n + 1;

  rep(i, 100) {

    c1 = (l * 2 + r) / 3;

    c2 = (r * 2 + l) / 3;

    f(c1) < f(c2) ? l = c1 : r = c2;

  }

  return f(l);

}



int main() {

  cin >> a >> b >> n;



  ll l = 0, r = n + 1;

  rep(i, 100) {

    c1 = (l * 2 + r) / 3;

    c2 = (r * 2 + l) / 3;

    g(c1) < g(c2) ? l = c1 : r = c2;

  }

  if (f(0) > f(r)) r = 0;

  else if (f(n) > f(r)) r = n;

  cout <<  f(r) << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;

const int INF = 1e9;



ll a, b, n, c1, c2, ans = 0;



ll f(ll x) { return floor(a * x / b) - a * floor(x / b); }



int main() {

  cin >> a >> b >> n;



  cout << f(min(b - 1, n)) << endl;

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;

const int INF = 1e9;



ll a, b, n, c1, c2, ans = 0;



ll f(ll x) { return floor(a * x / b) - a * floor(x / b); }



ll g(ll x) {

  ll l = 0, r = n;

  rep(i, 100) {

    c1 = (l * 2 + r) / 3;

    c2 = (r * 2 + l) / 3;

    f(c1) < f(c2) ? l = c1 : r = c2;

  }

  return f(l);

}



int main() {

  cin >> a >> b >> n;



  ll l = 0, r = n;

  rep(i, 100) {

    c1 = (l * 2 + r) / 3;

    c2 = (r * 2 + l) / 3;

    g(c1) < g(c2) ? l = c1 : r = c2;

  }

  if (f(0) > f(r)) r = 0;

  else if (f(n) > f(r)) r = n;

  cout <<  f(r) << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;

const int INF = 1e9;



ll a, b, n, c1, c2, ans = 0;



ll f(ll x) { return floor(a * x / b) - a * floor(x / b); }



int main() {

  cin >> a >> b >> n;

  cout << f(min(b - 1, n)) << endl;

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5 + 100;



int n, q, x[N];

ll sum[N], f[N], fen[2][N];



void update(int id, int p, ll val) {

  if (p <= 0) return;

  for (; p; p -= p & -p) fen[id][p] = min(fen[id][p], val);

}



ll query(int id, int p) {

  ll res = 1e18;

  if (p <= 0) return res;

  for (; p <= n; p += p & -p) res = min(res, fen[id][p]);

  return res;

}



int main() {

  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

  cin >> n >> q; q += 2;

  for (int i = 1; i <= q; ++i) {

    cin >> x[i];

    if (i > 1) sum[i] = sum[i - 1] + abs(x[i] - x[i - 1]);

  }

  memset(fen, 0x3f, sizeof(fen));

  for (int i = q - 1; i; --i) {

    f[i] = 1e18;

    f[i] = min(f[i], sum[q] - sum[i + 1] + f[q]);

    f[i] = min(f[i], query(0, x[i]) - x[i] - sum[i + 1]);

    f[i] = min(f[i], query(1, n + 1 - x[i]) + x[i] - sum[i + 1]);

    update(0, x[i + 1], f[i] + sum[i] + x[i + 1]);

    update(1, n + 1 - x[i + 1], f[i] + sum[i] - x[i + 1]);

  }

  cout << f[1];

  return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

const int MAXN = 200050;

int n, q, A, lst;

LL tag, mn[MAXN<<2][2];

void build(int i, int l, int r) {

	if(l == r) {

		mn[i][0] = abs(l-A) - l;

		mn[i][1] = abs(l-A) + l;

		return;

	}

	int mid = (l + r) >> 1;

	build(i<<1, l, mid);

	build(i<<1|1, mid+1, r);

	mn[i][0] = min(mn[i<<1][0], mn[i<<1|1][0]);

	mn[i][1] = min(mn[i<<1][1], mn[i<<1|1][1]);

}

LL qry(int i, int l, int r, int x, int y, int o) {

	if(x <= l && r <= y) return mn[i][o];

	int mid = (l + r) >> 1; LL re = 1ll<<60;

	if(x <= mid) re = min(re, qry(i<<1, l, mid, x, y, o));

	if(y > mid) re = min(re, qry(i<<1|1, mid+1, r, x, y, o));

	return re;

}

void upd(int i, int l, int r, int x, LL val) {

	if(l == r) {

		if(val < mn[i][0]+l+tag) {

			mn[i][0] = val-tag-l;

			mn[i][1] = val-tag+l;

		}

		return;

	}

	int mid = (l + r) >> 1;

	if(x <= mid) upd(i<<1, l, mid, x, val);

	else upd(i<<1|1, mid+1, r, x, val);

	mn[i][0] = min(mn[i<<1][0], mn[i<<1|1][0]);

	mn[i][1] = min(mn[i<<1][1], mn[i<<1|1][1]);

}

LL ans;

void dfs(int i, int l, int r) {

	if(l == r) {

		ans = min(ans, mn[i][0]+l+tag);

		return;

	}

	int mid = (l + r) >> 1;

	dfs(i<<1, l, mid);

	dfs(i<<1|1, mid+1, r);

}

int main () {

	scanf("%d%d%d%d", &n, &q, &lst, &A);

	build(1, 1, n);

	for(int i = 1, x; i <= q; lst = x, ++i) {

		scanf("%d", &x);

		LL val = qry(1, 1, n, 1, x, 0) + tag + x;

		if(x < n) val = min(val, qry(1, 1, n, x+1, n, 1) + tag - x);

		tag += abs(x-lst);

		upd(1, 1, n, lst, val);

	}

	ans = 1ll<<60;

	dfs(1, 1, n);

	printf("%lld\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



#define oo ll(1e16)

#define maxn 200005

#define block 400



using namespace std;

typedef long long ll;



int n, q, a, b;

ll d[maxn];

ll L[maxn], R[maxn];



ll ret = 0;



ll get(int st, int en, int ok) {

  ll ret = oo;



  for (int i = st; i <= en;)

    if (i % block == 1 && i + block <= en + 1) {

      ret = min(ret, (ok ? L[(i - 1) / block] : R[(i - 1) / block]));

      i += block;

    }

    else {

      ret = min(ret, d[i] + (ok ? -i : i));

      ++i;

    }



  return ret;

}



int main(){

  ios_base::sync_with_stdio(0);



  cin >> n >> q >> a >> b;



  fill(d + 1, d + n + 1, oo);

  fill(L, L + n + 1, oo);

  fill(R, R + n + 1, oo);



  d[b] = 0;

  L[(b - 1) / block] = -b;

  R[(b - 1) / block] = b;



  while (q--) {

    int x;

    cin >> x;



    ll tem = min(get(1, x, 1) + x, get(x, n, 0) - x);



    d[a] = min(d[a], tem - abs(x - a));



    int bl = (a - 1) / block;



    L[bl] = oo;

    R[bl] = oo;



    for (int i = max(bl * block + 1, 1); i <= bl * block + block && i <= n; ++i) {

      L[bl] = min(L[bl], d[i] - i);

      R[bl] = min(R[bl], d[i] + i);

    }



    ret += abs(x - a);



   // for (int i = 1; i <= n; ++i) cerr << d[i] + ret << ' '; cerr << "\n\n";



    a = x;

  }



  ll ma = 0;

  for (int i = 1; i <= n; ++i)

    ma = min(ma, d[i]);



  cout << ma + ret;



  return 0;



}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

const int MAXN = 200050;

int n, q, A, lst;

LL tag, mn[MAXN<<2][2];

void build(int i, int l, int r) {

	if(l == r) {

		mn[i][0] = abs(l-A) - l;

		mn[i][1] = abs(l-A) + l;

		return;

	}

	int mid = (l + r) >> 1;

	build(i<<1, l, mid);

	build(i<<1|1, mid+1, r);

	mn[i][0] = min(mn[i<<1][0], mn[i<<1|1][0]);

	mn[i][1] = min(mn[i<<1][1], mn[i<<1|1][1]);

}

LL qry(int i, int l, int r, int x, int y, int o) {

	if(x <= l && r <= y) return mn[i][o];

	int mid = (l + r) >> 1; LL re = 1ll<<60;

	if(x <= mid) re = min(re, qry(i<<1, l, mid, x, y, o));

	if(y > mid) re = min(re, qry(i<<1|1, mid+1, r, x, y, o));

	return re;

}

void upd(int i, int l, int r, int x, LL val) {

	if(l == r) {

		if(val < mn[i][0]+l+tag) {

			mn[i][0] = val-tag-l;

			mn[i][1] = val-tag+l;

		}

		return;

	}

	int mid = (l + r) >> 1;

	if(x <= mid) upd(i<<1, l, mid, x, val);

	else upd(i<<1|1, mid+1, r, x, val);

	mn[i][0] = min(mn[i<<1][0], mn[i<<1|1][0]);

	mn[i][1] = min(mn[i<<1][1], mn[i<<1|1][1]);

}

LL ans;

void dfs(int i, int l, int r) {

	if(l == r) {

		ans = min(ans, mn[i][0]+l+tag);

		return;

	}

	int mid = (l + r) >> 1;

	dfs(i<<1, l, mid);

	dfs(i<<1|1, mid+1, r);

}

int main () {

	scanf("%d%d%d%d", &n, &q, &lst, &A);

	build(1, 1, n);

	for(int i = 1, x; i <= q; lst = x, ++i) {

		scanf("%d", &x);

		LL val = qry(1, 1, n, 1, x, 0) + tag + x;

		if(x < n) val = min(val, qry(1, 1, n, x+1, n, 1) + tag - x);

		tag += abs(x-lst);

		upd(1, 1, n, lst, val);

	}

	ans = 1ll<<60;

	dfs(1, 1, n);

	printf("%lld\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"



#define REP(i,num) for(int i=0;i<(num);++i)

#define LOOP(i) while(i--)

#define ALL(c) c.begin(),c.end()

#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;

#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}



using namespace std;

using ll = long long;



constexpr ll atcoder_mod = 1e9+7;



template<typename T=int>

T in(){T x; cin >> x; return (x);}

template<typename T=int,typename C=vector<T>>

C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}



void vout(){cout << endl;}

template<typename Head,typename... Tail>

void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}

void out(){cout << endl;}

template<typename Head,typename... Tail>

void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}



int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	cout<<fixed<<setprecision(10);

	

	string S=in<string>();

	int N=S.size();



	vector<vector<short>> dp(N+1,vector<short>(2019,0));

	dp[0][0] = 0;

	REP(i,N){

		int M=S[i]-'0';

		dp[i+1][M] += 1;

		REP(j,2019){

			int V=j*10+(S[i]-'0');

			M=V%2019;

			dp[i+1][M] += dp[i][j];

		}

	}

	

	int sum=0;

	REP(i,N+1){

		sum+=dp[i][0];

	}

	out(sum);

	return 0;

}


// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"



#define REP(i,num) for(ll i=0;i<(num);++i)

#define LOOP(i) while(i--)

#define ALL(c) c.begin(),c.end()

#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;

#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}



using namespace std;

using ll = long long;

using vll = vector<ll>;

using vvll = vector<vector<ll>>;



constexpr ll atcoder_mod = 1e9+7;



template<typename T=ll>

T in(){T x; cin >> x; return (x);}

template<typename T=ll,typename C=vector<T>>

C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}



void vout(){cout << endl;}

template<typename Head,typename... Tail>

void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}

void out(){cout << endl;}

template<typename Head,typename... Tail>

void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}



template<typename T>

bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

template<typename T>

bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}



ll powermod(ll a,ll b,ll m){

	if(b==0){

		return 1LL;

	}

	if(b%2){

		return (a*powermod(a,b-1LL,m))%m;

	}

	return powermod((a*a)%m,b/2LL,m);

}



int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	cout<<fixed<<setprecision(10);



	string S=in<string>();

	int N=S.size();

	vector<int> M(N+1,0);

	reverse(ALL(S));

	REP(i,N){

		int V=M[i];

		int X=(S[i]-'0')*powermod(10,i,2019);

		M[i+1] = (X+V)%2019;

	}

	map<int,ll> C;

	REP(i,N+1){

		C[M[i]]++;

	}

	ll A=0;

	for(auto& x:C){

		A += x.second*(x.second-1LL)/2LL;

	}

	out(A);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double PI = 3.1415926535897932;   // acos(-1)

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

#define chmin(x, y) x = min(x, y)



constexpr int m = 2019;



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    string s;

    cin >> s;

    int n = s.length();

    

    vector<ll> dp(m, 0);

    dp[0] = 1;

    ll ans = 0;

    for(int i = 0; i < n; ++i){

        int num = s[i] - '0';

        vector<ll> nextdp(m, 0);

        for(int j = 0; j < m; ++j){

            if(!dp[j])  continue;

            int nj = (j * 10 + num) % m;

            nextdp[nj] += dp[j];

        }

        dp = nextdp;

        ans += dp[0]++;

    }

    cout << ans << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



template<class T>

inline bool chmax(T& x, T y){

    if(x < y){

        x = y;

        return true;

    }

    return false;

}

template<class T>

inline bool chmin(T& x, T y){

    if(x > y){

        x = y;

        return true;

    }

    return false;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    string s;

    cin >> s;

    int n = s.length();

    reverse(s.begin(), s.end());

    vector<int> S(n + 1);

    S[0] = 0;

    int mul = 1;

    constexpr int m = 2019;

    for(int i = 0; i < n; ++i){

        int x = s[i] - '0';

        x = x * mul % m;

        mul = mul * 10 % m;

        S[i + 1] = (S[i] + x) % m;

    }

    vector<int> c(m, 0);

    ll ans = 0;

    for(int i = 0; i <= n; ++i){

        ans += c[S[i]]++;

    }

    cout << ans << endl;

}

// Fastest known solution for this problem: