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;
  struct cp {
    double x, y;
    cp(double a = 0, double b = 0) { x = a, y = b; }
    inline cp operator+(cp &a) { return cp{x + a.x, y + a.y}; }
    inline cp operator-(cp &a) { return cp{x - a.x, y - a.y}; }
    inline cp operator*(cp &a) {
      return cp{x * a.x - y * a.y, x * a.y + y * a.x};
    }
    inline void operator/=(double a) { x /= a, y /= a; }
    inline void operator+=(cp &a) { x += a.x, y += a.y; }
    inline cp conj() { return cp(x, -y); }
  };
  const double PI = acos(-1.0);
  const int maxn = 800005;
  cp w[maxn], A[maxn], B[maxn];
  void fft(cp *a, int n, int f = 0) {
    for (int i = 0, j = 0; i < n; ++i) {
      if (i > j) swap(a[i], a[j]);
      for (int l = n >> 1; (j ^= l) < l; l >>= 1)
        ;
    }
    w[0] = cp(1, 0);
    for (int l = 2; l <= n; l <<= 1) {
      cp g = cp(cos(2 * PI / l), sin(2 * PI / l));
      if (f) g = g.conj();
      for (int j = (l >> 1); j >= 0; j -= 2) w[j] = w[j >> 1];
      for (int j = 1; j < (l >> 1); j += 2) w[j] = w[j - 1] * g;
      int m = l / 2;
      for (int j = 0; j != n; j += l) {
        for (int i = 0; i < m; ++i) {
          cp tmp = w[i] * a[j + i + m];
          a[j + i + m] = a[i + j] - tmp, a[i + j] = a[i + j] + tmp;
        }
      }
    }
    if (f)
      for (int i = 0; i < n; ++i) a[i] /= n;
  }
  const int mod = 1e9 + 7;
  void mul(vector<long long> &a, vector<long long> &b) {
    if (max(a.size(), b.size()) < 128) {
      int sza = a.size(), szb = b.size(), len = sza + szb - 1;
      vector<long long> ret(len);
      for (int i = 0; i < sza; i++)
        for (int j = 0; j < szb; j++) ret[i + j] += a[i] * b[j] % mod;
      a.resize(len);
      for (int i = 0; i < len; ++i) a[i] = ret[i] % mod;
      while (len > 0 && !a[len - 1]) --len;
      a.resize(len);
      return;
    }
    int m = a.size() + b.size(), len = 1;
    for (; len <= m; len <<= 1)
      ;
    for (int i = 0; i < a.size(); ++i) A[i] = a[i];
    for (int i = 0; i < b.size(); ++i) B[i] = b[i];
    for (int i = a.size(); i <= len; ++i) A[i] = 0;
    for (int i = b.size(); i <= len; ++i) B[i] = 0;
    fft(A, len);
    fft(B, len);
    for (int i = 0; i < len; ++i) A[i] = A[i] * B[i];
    fft(A, len, -1);
    a.resize(len);
    for (int i = 0; i < len; ++i) a[i] = (long long)(A[i].x + 0.5) % mod;
    while (len > 0 && !a[len - 1]) --len;
    a.resize(len);
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    if (k == 1) {
      long long p = 1ll * n * m % mod;
      long long ans = p * (p + 1) / 2 % mod + (p - 2) * (p - 1) / 2 % mod;
      ans %= mod;
      cout << ans << '\n';
      return 0;
    }
    vector<int> a(n), pre(n + 1), suf(n + 1);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) {
      pre[i + 1] = (pre[i] + a[i]) % k;
    }
    for (int i = n - 1; i >= 0; --i) {
      suf[i] = (suf[i + 1] + a[i]) % k;
    }
    int sum = pre[n];
    vector<long long> b(k), c(k);
    for (int i = 1; i <= n; ++i) {
      b[pre[i]] += 1;
    }
    for (int i = 0; i <= n - 1; ++i) {
      c[suf[i]] += 1;
    }
    mul(b, c);
    for (int i = k; i < b.size(); ++i) {
      (b[i % k] += b[i]) %= mod;
    }
    b.resize(k);
    auto solve1 = [&](int x) {
      vector<int> cnt(k);
      long long ret = 0;
      for (int i = 0; i <= n; ++i) {
        ret += cnt[(pre[i] - x + k) % k];
        cnt[pre[i]] += 1;
      }
      return ret % mod;
    };
    auto solve2 = [&](int x, int d) {
      x = (x - 1ll * (d - 1) * sum % k + k) % k;
      long long ret = b[x];
      return ret % mod;
    };
    long long ans = solve1(0) * m % mod;
    for (int i = 1; i <= m - 1; ++i) {
      ans += solve2(0, i) * (m - i) % mod;
    }
    long long r = 1ll * sum * m % k;
    ans += solve1(r) * m % mod;
    for (int i = 1; i <= m - 1; ++i) {
      ans += solve2(r, i) * (m - i) % mod;
    }
    vector<int> cnt1(k);
    for (int i = 1; i <= n; ++i) {
      cnt1[pre[i]] += 1;
    }
    ans -= cnt1[r];
    for (int i = 1; i < m; ++i) {
      ans -= cnt1[(r - 1ll * i * sum % k + k) % k];
    }
    vector<int> cnt2(k);
    for (int i = n - 1; i >= 0; --i) {
      cnt2[suf[i]] += 1;
    }
    ans -= cnt2[r];
    for (int i = 1; i < m; ++i) {
      ans -= cnt2[(r - 1ll * i * sum % k + k) % k];
    }
    ans += 1;
    ans %= mod;
    if (ans < 0) ans += mod;
    cout << ans << '\n';
  }
  