description: Denote a cyclic sequence of size n as an array s such that s_n is adjacent to s_1. The segment s[r, l] where l < r is the concatenation of s[r, n] and s[1, l].
  
  You are given an array a consisting of n integers. Define b as the cyclic sequence obtained from concatenating m copies of a. Note that b has size n ⋅ m.
  
  You are given an integer k where k = 1 or k is a prime number. Find the number of different segments in b where the sum of elements in the segment is divisible by k.
  
  Two segments are considered different if the set of indices of the segments are different. For example, when n = 3 and m = 2, the set of indices for segment s[2, 5] is \{2, 3, 4, 5\}, and for segment s[5, 2] is \{5, 6, 1, 2\}. In particular, the segments s[1, 6], s[2,1], …, s[6, 5] are considered as the same segment.
  
  Output the answer modulo 10^9 + 7.
  
  Input
  
  The first line contains three integers n, m, and k (1 ≤ n, m, k ≤ 2 ⋅ 10^5, k = 1 or k is a prime number).
  
  The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 2 ⋅ 10^5).
  
  Output
  
  Output an integer denoting the number of different segments in b where the sum of elements in the segment is divisible by k, modulo 10^9 + 7.
  
  Examples
  
  Input
  
  
  5 1 5
  1 2 3 4 3
  
  
  Output
  
  
  4
  
  
  Input
  
  
  5 1 5
  1 2 3 4 5
  
  
  Output
  
  
  5
  
  
  Input
  
  
  5 4 5
  1 2 3 4 5
  
  
  Output
  
  
  125
  
  Note
  
  In the first example, all valid segments are [1,4], [2, 3], [3, 5], and [4, 2].
  
  In the second example, one of the valid segments is [1, 5].
solution: #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  const int mod = 1e9 + 7;
  int n, m, k, a[200200], s[200200], id[200200];
  ll c[200200], pl[400400], ans;
  int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = (s[i - 1] + a[i]) % k;
    int p = s[n];
    if (!p) {
      for (int i = 1; i <= n; i++) c[s[i]] += m;
    } else {
      vector<int> v;
      for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
      for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
      for (int i = 0; i < k; i++) id[v[i]] = i;
      for (int i = 1; i <= n; i++) {
        pl[0] += m / k, pl[k] -= m / k;
        int u = id[s[i] % k];
        pl[u]++, pl[u + m % k]--;
      }
      for (int i = 0; i < 2 * k; i++) {
        if (i) pl[i] += pl[i - 1];
        c[v[i]] += pl[i];
      }
    }
    for (int i = 1; i <= n; i++) {
      c[s[i]]--;
      int x = (1ll * p * m % k + s[i]) % k;
      (ans += c[x]) %= mod;
      c[x]++;
    }
    (ans *= m) %= mod;
    if (1ll * p * m % k == 0) ans = (ans + 1) % mod;
    cout << ans;
  }
  