For convenience, let reassign the index \((k-1)\) to rest area \(k\) to treat indices from \(0\) through \((N-1)\).

Consider the following array.

Let \(R_i=\) (the number of steps, modulo \(M\), required to travel from rest area \(0\) to rest area \(i \% N\) as the \(i\)-th rest area to encounter). Precalculate these values for \(i\) from \(0\) through \(2N-1\).
For example, if \(A=(1,2,3,4)\) and \(M=6\), then \(R=(0,1,3,0,4,5,1,4)\).

When is the minimum steps required to travel from \(s\) to \(t\) (\(s \neq t\)) a multiple of \(M\)?

• If \(s<t\), it holds when \(R_s = R_t\).
  • This is equivalent to \(R_{N+s}=R_{N+t}\).
• If \(s>t\), it holds when \(R_s = R_{N+t}\).

Therefore, it is sufficient to solve the following problem:

Find the sum of the following value for \(i=N,N+1,\dots,2N-1\).

• How many elements among \(R_{i-N+1},R_{i-N+2},\dots,R_{i-1}\) are equal to \(R_i\)?

Intuitively, we are summing up the number of rest areas \(i \% N\) to which the minimum steps required is a multiple of \(M\), over \(i=N,N+1,\dots,2N-1\).

This problem can be solved as follows:

• First, let \(B=(B[0],B[1],\dots,B[M-1])\) be the array of occurrences of \(k\) between \(0\) and \(M-1\) in \(R_0\) through \(R_{N-1}\).
• For \(i = N,N+1,\dots,2N-1\), repeat the following:
  • Decrease \(B[R_{i-N}]\) by one.
    • This makes the current \(B\) manage the occurrences between \(i-N+1\) and \(i-1\).
  • Add \(B[R_{i}]\)
  • Increase \(B[R_{i}]\) by one.
    • This makes the current \(B\) manage the occurrences between \(i-N+1\) and \(i\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  vector<int> r={0};
  for(int i=0;i<2*n;i++){
    r.push_back((r.back()+a[i%n])%m);
  }
  vector<int> b(m,0);
  for(int i=0;i<n;i++){b[r[i]]++;}
  long long res=0;
  for(int i=n;i<2*n;i++){
    b[r[i-n]]--;
    res+=b[r[i]];
    b[r[i]]++;
  }
  cout << res << "\n";
  return 0;
}