stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int limit = 100010;

using edge = struct {int to; long long int cost;};

vector<edge> tree[limit];

long long int depth[limit];

 

void bfs(int v, int p, long long int d) {

    // v = 次の場所

	// p = 前の場所

	queue<edge> Q;

	Q.push({v,0});

    //printf("%d, %d, %lld\n", p+1, v+1, d);

	//スタート地点の枝分かれ箇所数だけ繰り返す。

	while(Q.size() != 0){

		//printf("size: %d",Q.size());

		//puts("");

		edge p = Q.front(); Q.pop();

		depth[p.to] = p.cost;

		//cout << "depth:" << p.to+1 << "=" << p.cost <<endl;

		for( int i = 0; i < tree[p.to].size(); i++){

			if(depth[tree[p.to][i].to] == 1000000000000000 ) {

				Q.push({tree[p.to][i].to,tree[p.to][i].cost + depth[p.to]});

				//printf("push: {%d, %d}",tree[p.to][i].to+1, tree[p.to][i].cost + depth[p.to]);

				//puts("");

			}

		}

	}

}

 

int main(void) {

	int n;

	cin >> n;

 

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

		depth[i] = 1000000000000000;

	}

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

		int a, b, c;

		cin >> a >> b >> c;

		a--, b--;

		tree[a].push_back({b, c});

        tree[b].push_back({a, c});

    }

    //puts("");

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

        for( int j = 0; j < tree[i].size(); j++){

            //cout << i+1 << "," << tree[i][j].to+1 << "," << tree[i][j].cost << endl;

        }

    }

    //puts("");

	int q, k;

	cin >> q >> k;

	k--;

 

	bfs(k, -2, 0);

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

		int x, y;

		cin >> x >> y;

		x--, y--;

        cout << depth[x] + depth[y] << endl;

        //printf("depth[%d] = %lld\ndepth[%d] = %lld\n", x, depth[x], y, depth[y]);

	}

 

	return 0;

}

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

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF2 1000000000000000000

#define INF 2000000000

#define int long long int

struct edge { int to, cost; };

typedef pair<int, int> P;



int V;

vector<edge> G[100010];

int d[100010];



void dijkstra(int s) {

    priority_queue<P, vector<P>, greater<P> > que;

    fill(d, d + V + 1, INF2);

    d[s] = 0;

    que.push(P(0, s));



    while (!que.empty()) {

        P p = que.top(); que.pop();

        int v = p.second;

        if (d[v] < p.first) continue;

        for (int i = 0; i < G[v].size(); i++){

            edge e = G[v][i];

            if (d[e.to] > d[v] + e.cost) {

                d[e.to] = d[v] + e.cost;

                que.push(P(d[e.to], e.to));

            }

        }

    }

}



signed main(void)

{

    cin >> V;

    rep(i ,V-1){

        int s, t, c;

        cin >> s >> t >> c;

        G[s].push_back({t, c});

        G[t].push_back({s, c});

    }

    int Q,K;

    cin >> Q >> K;

    dijkstra(K);

    int x[Q], y[Q];

    rep(i, Q) cin >> x[i] >> y[i];

    rep(i ,Q) cout << d[x[i]] + d[y[i]] << endl;

    return 0;

}

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

using namespace std;

typedef pair<int,int> P;

typedef long long ll;

typedef long double ld;

const int inf=1e9+7;

const ll longinf=1LL<<60;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

#define F first

#define S second



const int mx=100010;

const ll mod=1e9+7;



vector<vector<int>> g(mx);

vector<ll> dp(mx,-1);

map<P,int> mp;



int main(){

  int n; cin >> n;

  for(int i=1,a,b,c; i<n; i++){

    cin >> a >> b >> c;

    a--; b--;

    g[a].emplace_back(b);

    g[b].emplace_back(a);

    mp[make_pair(a,b)] = mp[make_pair(b,a)] = c;

  }

  int q,k; cin >> q >> k; k--;



  queue<int> que; que.emplace(k);

  dp[k]=0;



  while(!que.empty()){

    int v=que.front(); que.pop();

    for(int u:g[v]){

      if(dp[u] != -1){ continue; }

      dp[u] = dp[v] + mp[make_pair(u,v)];

      que.emplace(u);

    }

  }



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

      int x,y; 

      cin >> x >> y; x--; y--;

    cout << dp[x]+dp[y] << endl;

  }



  return 0;   

}


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

using namespace std;

typedef pair<int,int> P;

typedef long long ll;

typedef long double ld;

const int inf=1e9+7;

const ll longinf=1LL<<60;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

#define F first

#define S second



const int mx=100010;

const ll mod=1e9+7;



typedef vector<vector<pair<ll,int>>> wgraph;

typedef pair<ll,int> pli;



vector<ll> bfs(wgraph v,int x){

  priority_queue<pli,vector<pli>,greater<pli>> q;

  vector<ll> dist(v.size(),longinf);

  dist[x]=0;

  q.push({0LL,x});

  

  while(q.size()){

    pli p=q.top(); q.pop();

    ll d=p.F, now=p.S;

    if(dist[now]<d){ continue; }

    for(auto to:v[now]){

      if(dist[to.S]>d+to.F){

        dist[to.S] = d+to.F;

        q.push({dist[to.S], to.S});

      }

    }

  }

  return dist;

}



int main(){

  int n;

  cin >> n;

  wgraph v(n);

  rep(i,n-1){

    int x,y,c;

    cin >> x >> y >> c; x--; y--;

    v[x].push_back({c,y});

    v[y].push_back({c,x});

  }

  int q,k; cin >> q >> k; k--;

  vector<ll> data=bfs(v,k);

  rep(i,q){

    int x,y;

    cin >> x >> y; x--; y--;

    cout << data[x]+data[y] << endl;

  }

  return 0;

}


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

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

#define repb(i, a, b) for(int i = a; i >= b; i--)

#define all(a) a.begin(), a.end()

#define o(a) cout << a << endl

#define int long long

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

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

using namespace std;

typedef pair<int, int> P;

const int mod = 1000000007;

const int INF = 1e16;

struct edge{

    int to, cost;

    edge(int to, int cost):to(to), cost(cost){}

};

const int V = 100010;

vector<edge> G[100010];

int d[100010];



void dijkstra(int s){

    fill(d, d + V, INF);//V, INF

    d[s] = 0;

    priority_queue<P, vector<P>, greater<P> > q;

    q.push(P(d[s], s));

    while(!q.empty()){

        P p = q.top(); q.pop();

        int from = p.second;

        int cost = p.first;

        if(d[from] < cost) continue;

        rep(i, 0, G[from].size()){

            edge e = G[from][i];

            int next = e.to;

            int newCost = e.cost + cost;

            if(d[next] > newCost){

                d[next] = newCost;

                q.push(P(newCost, next));

            }

        }

    }

}



signed main(){

    int n, q, k;

    cin >> n;

    rep(i, 0, n - 1){

        int a, b, c;

        cin >> a >> b >> c;

        a--; b--;

        G[a]. push_back({b, c});

        G[b]. push_back({a, c});        

    }

    cin >> q >> k;

    k--;

    dijkstra(k);

    rep(i, 0, q){

        int x, y;

        cin >> x >> y;

        x--; y--;

        cout << d[x] + d[y] << endl;

    }

}

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

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

#define REP(i, n) rep(i, 0, n)

#define repb(i, a, b) for(int i = a; i >= b; i--)

#define all(a) a.begin(), a.end()

#define int long long

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

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

using namespace std;

typedef pair<int, int> P;

const int mod = 1000000007;

const int INF = 1e12;



int n, q, k;

vector<P> G[100010];

int d[100010];



void dfs(int now, int pre, int l){

    d[now] = l;

    rep(i, 0, G[now].size()){

        int next = G[now][i].first;

        if(pre == next) continue;

        dfs(next, now, l + G[now][i].second);

    }

}



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n;

    rep(i, 0, n - 1){

        int a, b, c;

        cin >> a >> b >> c;

        a--; b--;

        G[a].push_back(P(b, c));

        G[b].push_back(P(a, c));

    }

    cin >> q >> k;

    k--;

    dfs(k, -1, 0);

    rep(i, 0, q){

        int x, y;

        cin >> x >> y;

        x--; y--;

        cout << d[x] + d[y] << endl;

    }

}

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

#include <algorithm>

#include <cmath>

#include <iomanip>

using namespace std;



bool eq(double x,double y){

  if(abs(x-y)<0.00001*y)return true;

  else return false;

}



int main(void){

    long long q;

    double x[100], x1;

    while(cin >> q){

        if(q == -1) break;

        x[1] = q/2.0;

        for(int i = 2; ; i++){

            x[i] = x[i-1]-(x[i-1]*x[i-1]*x[i-1]-(double)q)/(3*x[i-1]*x[i-1]);

            if(eq(x[i]*x[i]*x[i],(double)q)){

                x1 = x[i]; 

                break;

            }

        }

        cout <<fixed;

        cout << setprecision(7) << x1 << endl;

    } 

    return 0;

}




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

#include <math.h>

int main(void){

    double q; 

    while(scanf("%lf", &q)!= EOF && q != -1) { 

        double x, a;       

        x=q/2;       

            while(1){

                if(fabs(x*x*x-q)<0.00001*q) break;

                x=x-((x*x*x-q)/(3*x*x));

                x = x;

            }          

            printf("%.7f\n",x);     

            }    

                

        return 0; 

}


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



using namespace std;

typedef long long LL;



const int MAXN = 123456;

LL presum[MAXN];

vector<LL> line[MAXN];

map<LL, int> mp;



LL cal(LL cur, LL mod) {

   if (cur >= mod)

      return (cur - mod) % mod;

   else

      return (mod - cur) % mod;

}



int main() {

    int N, M;

    scanf("%d %d", &N, &M);

    int idx = 0;

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

        int tmp;

        scanf("%d", &tmp);

        presum[i] = presum[i - 1] + tmp;

        presum[i] %= M;

        if (!mp.count(presum[i])) mp[presum[i]] = idx++;

        line[mp[presum[i]]].push_back(i);

    }

    LL ans = 0;

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

        LL tmp = cal(-presum[i - 1], M);

        // printf("i = %d tmp = %lld\n", i, tmp);

        if (mp.count(tmp)) {

           LL cur = mp[tmp];

           auto low = lower_bound(line[cur].begin(), line[cur].end(), i);

           ans += LL(line[cur].end() - low);

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

        }

    }

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

    return 0;

}


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



using namespace std;

typedef long long LL;



const int MAXN = 123456;

map<LL, int> mp;



int main() {

    int N, M;

    scanf("%d %d", &N, &M);

    LL ans = 0, presum = 0;

    mp[0] = 1;

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

        int tmp;

        scanf("%d", &tmp);

        presum = (presum + tmp) % M;

        ans += mp[presum];

        mp[presum]++;

    }

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

    return 0;

}


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

#define ll long long

#define ms(a, b) memset(a, b, sizeof(a))



using namespace std;



const int Size = 26;

const int MAXN = 1e5 + 100;

const int maxn = 50 + 7;

const int MOD = 1e5;

const int INF = 0x3FFFFFFF;



set<int>s;

map<int, int>mp;

int pre[MAXN], a[MAXN];



int main()

{

    int n;

    ll m;

    ll ans = 0;

    ll temp;

    ios::sync_with_stdio(false);

    s.clear();

    mp.clear();

    cin >> n >> m;

    pre[0] = 0;

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

    {

        cin >> a[i];

        pre[i] = a[i];

    }

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

    {

        pre[i] = (pre[i - 1] + pre[i]) % m;

        mp[pre[i]]++;

        if(!s.count(pre[i]))   s.insert(pre[i]);

    }

    set<int>::iterator it;

    for(it = s.begin(); it != s.end(); it++)

    {

        temp = mp[*it];

        ans += temp * (temp - 1) / 2;

    }

    if(*s.begin() == 0)

        ans += mp[0];

    cout << ans << endl;

    return 0;

}


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

#include<map>

using namespace std;

typedef long long ll;

ll a[110000];

ll sum[110000];

map<ll,ll>cnt;

int main()

{

    ll n,m;

    sum[0]=0;

    scanf("%lld%lld",&n,&m);

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

    {

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

        sum[i]=(sum[i-1]+a[i])%m;

    }

    ll ans=0;

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

    {

            ans+=cnt[sum[i]];

            cnt[sum[i]]++;

    }

    printf("%lld\n",ans+cnt[0]);

    return 0;

}


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



using namespace std;

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





int main()

{

	int N,M;

	cin >> N >> M;



	int A[100001] = {};

	long long B[100001] = {};

	map<int, int> MAP;



	repeat(i, N) {

		cin >> A[i];

		B[i + 1] = B[i] + A[i];



		B[i + 1] %= M;



		MAP[(int)B[i + 1]]++;

	}

	MAP[0]++;



	long long result = 0;



	for (auto ITR : MAP){

		result += 1ll * ITR.second * (ITR.second - 1) / 2;

	}





	//出力

	cout << result << endl;













	return 0;

}

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

#include<cstdio>

using namespace std;

typedef long long ll;

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

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



void pakuri_sort(int N, int A[]) {

	const int b = 8;

	int tmp[200001];

	rep(k, 4) {

		int kazu[1 << b] = {}, kazu2[1 << b] = {};

		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];

		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];

		k++;

		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];

		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];

	}

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint(), M = getint();

	int A[100001];

	A[0] = 0;

	rep1(i, N) {

		int a = getint();

		A[i] = (A[i - 1] + a) % M;

	}

	pakuri_sort(N, A + 1);



	//数だけでええんか

	int mae = -1;

	int k = 0;

	ll kotae = 0;

	rep(i, N + 1) {

		if (mae != A[i]) k = 0;

		kotae += k++;

		mae = A[i];

	}

	printf("%lld", kotae);



	Would you please return 0;

}

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

using namespace std;

typedef long long ll;

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

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint(), M = getint();

	int S[100001];

	S[0] = 0;

	rep(i, N) {

		S[i + 1] = (S[i] + getint()) % M;

	}

	sort(S, S + N + 1);



	int mae = 0;

	ll k = 1;

	ll kotae = 0;

	rep1(i, N) {

		if (mae == S[i]) k++;

		else {

			kotae += k * (k - 1) / 2;

			mae = S[i];

			k = 1;

		}

	}

	kotae += k * (k - 1) / 2;



	co(kotae);



	Would you please return 0;

}

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

#include<cstdio>

using namespace std;

typedef long long ll;

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

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



void pakuri_sort(int N, int A[]) {

	const int b = 8;

	int tmp[200001];

	rep(k, 4) {

		int kazu[1 << b] = {}, kazu2[1 << b] = {};

		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];

		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];

		k++;

		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];

		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];

	}

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint(), M = getint();

	int A[100001];

	A[0] = 0;

	rep1(i, N) {

		int a = getint();

		A[i] = (A[i - 1] + a) % M;

	}

	pakuri_sort(N, A + 1);



	//数だけでええんか

	int mae = -1;

	int k = 0;

	ll kotae = 0;

	rep(i, N + 1) {

		if (mae != A[i]) k = 0;

		kotae += k++;

		mae = A[i];

	}

	printf("%lld", kotae);



	Would you please return 0;

}

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

using namespace std;

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

#define REP(i,a,n) for(ll i=a;i<n;i++)

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

#define P pair<ll,ll>

#define vl vector<ll>

#define vl vector<ll>

#define vvl vector<vector<ll>>

#define vvl vector<vector<ll>>

#define print(n) cout<<n<<endl

const int M=100010;

const int inf=1000000007;

const long long INF=1000000000000000007;

using ll=long long;

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};



ll comb(ll x){

	ll ans=1;

	ans=x*(x-1)/2;

	return ans;

}



int main(){

	ll n,m,ans=0;

	int a,dp[M]={};

	cin>>n>>m;

	rep(i,n){

		cin>>a;

		dp[i+1]=(dp[i]+a)%m;

	}

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

	REP(i,1,n+1){

		if(dp[i]==0)ans++;

		else break;

	}

	REP(i,1,n+1){

		ll cnt=1;

		REP(j,i+1,n+1){

			if(dp[i]==dp[j])cnt++;

			else break;

		}

		ans+=comb(cnt);

		i+=cnt-1;

	}

	print(ans);

}

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

using namespace std;

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

#define REP(i,a,n) for(ll i=a;i<n;i++)

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

#define P pair<ll,ll>

#define vl vector<ll>

#define vl vector<ll>

#define vvl vector<vector<ll>>

#define vvl vector<vector<ll>>

#define print(n) cout<<n<<endl

const int M=100010;

const int inf=1000000007;

const long long INF=1000000000000000007;

using ll=long long;

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};



int main(){

	ll n,m;

	cin>>n>>m;

	ll s=0;

	map<ll,ll> mp;

	REP(i,1,n+1){

		ll x;

		cin>>x;

		s+=x;

		mp[s%m]+=1;

	}

	ll ans=0;

	for(auto v:mp) {

		if(v.first==0)ans+=v.second;

		ans+=(v.second)*(v.second-1)/2;

	}

	print(ans);

}

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

#include<vector>

#include<stdlib.h>

#include<time.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#include<queue>

#include<map>

using namespace std;



int main(void){

 int l,r;

 long long int N,M,a;

 long long int ans=0;

 long long int sum=0;

 long long int A[100050]; 

 map<long long int,long long int> B;



 for(int i=0; i<=100020;i++)A[i]=0;



 cin>>N>>M;

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

  cin>>a;

  A[i+1]=(A[i]+a)%M;

 }



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

  ans+=B[A[i]];

  B[A[i]]++;

 }

 std::cout<<ans<<std::endl; 

}

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

#include<vector>

#include<stdlib.h>

#include<time.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#include<queue>

#include<map>

using namespace std;



int main(void){

 int N,M,a;

 map<int,int> B; 

 long long int ans=0;



 cin>>N>>M;

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

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

  cin>>a;

  A[i]=(A[i-1]+a)%M;

 }

 for(int i=0; i<N+1; i++){

  ans+=B[A[i]];

  B[A[i]]++;

 }

 std::cout<<ans<<std::endl;

}


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

#include<algorithm>

using namespace std;

typedef long long unsigned int ll;







int main(){

    int n;

    cin>>n;

    ll m;

    cin>>m;

    ll a[100005];

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

        cin>>a[i];

        a[i]%=m;

    }

    

    

    map<ll,ll> mod;

    ll sum[100005]={0};

    

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

        sum[i+1]=a[i]+sum[i];

        sum[i+1]%=m;

        

    }

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

        mod[sum[i]]++;

    }

    ll ans=0;

    for(auto i : mod){

        ans += (i.second*(i.second - 1)) / 2;

    }

    

    cout<<ans<<endl;

    return 0;

}




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

#include<algorithm>

using namespace std;

typedef long long unsigned int ll;







int main(){

    int n;

    cin>>n;

    ll m;

    cin>>m;

    ll a[100005];

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

        cin>>a[i];

        a[i]%=m;

    }

    

    

    map<ll,ll> mod;

    ll sum[100005];

    sum[0]=0;

    mod[0]=1;

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

        sum[i+1]=a[i]+sum[i];

        sum[i+1]%=m;

        mod[sum[i+1]]++;

    }

   

    ll ans=0;

    for(auto i : mod){

        ans += (i.second*(i.second - 1)) / 2;

    }

    

    cout<<ans<<endl;

    return 0;

}




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

#include<algorithm>

using namespace std;

typedef long long unsigned int ll;







int main(){

    int n;

    cin>>n;

    ll m;

    cin>>m;

    ll a[100005];

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

        cin>>a[i];

        a[i]%=m;

    }

    

    

    map<ll,ll> mod;

    ll sum[100005]={0};

    

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

        sum[i+1]=a[i]+sum[i];

        sum[i+1]%=m;

        

    }

    mod[0]=1;

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

        mod[sum[i]]++;

    }

    ll ans=0;

    for(auto i : mod){

        ans += (i.second*(i.second - 1)) / 2;

    }

    

    cout<<ans<<endl;

    return 0;

}




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

#include<algorithm>

using namespace std;

typedef long long unsigned int ll;







int main(){

    int n;

    cin>>n;

    ll m;

    cin>>m;

    ll a[100005];

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

        cin>>a[i];

        a[i]%=m;

    }

    

    

    map<ll,ll> mod;

    ll sum[100005];

    sum[0]=0;

    mod[0]=1;

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

        sum[i+1]=a[i]+sum[i];

        sum[i+1]%=m;

        mod[sum[i+1]]++;

    }

   

    ll ans=0;

    for(auto i : mod){

        ans += (i.second*(i.second - 1)) / 2;

    }

    

    cout<<ans<<endl;

    return 0;

}




// Fastest known solution for this problem: