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;
  constexpr long long mod = 1000000007;
  const long long INF = mod * mod;
  const double eps = 1e-8;
  const double pi = acosl(-1.0);
  long long mod_pow(long long x, long long n, long long m = mod) {
    if (n < 0) {
      long long res = mod_pow(x, -n, m);
      return mod_pow(res, m - 2, m);
    }
    if (abs(x) >= m) x %= m;
    if (x < 0) x += m;
    long long res = 1;
    while (n) {
      if (n & 1) res = res * x % m;
      x = x * x % m;
      n >>= 1;
    }
    return res;
  }
  struct modint {
    long long n;
    modint() : n(0) { ; }
    modint(long long m) : n(m) {
      if (n >= mod)
        n %= mod;
      else if (n < 0)
        n = (n % mod + mod) % mod;
    }
    operator int() { return n; }
  };
  bool operator==(modint a, modint b) { return a.n == b.n; }
  modint operator+=(modint& a, modint b) {
    a.n += b.n;
    if (a.n >= mod) a.n -= mod;
    return a;
  }
  modint operator-=(modint& a, modint b) {
    a.n -= b.n;
    if (a.n < 0) a.n += mod;
    return a;
  }
  modint operator*=(modint& a, modint b) {
    a.n = ((long long)a.n * b.n) % mod;
    return a;
  }
  modint operator+(modint a, modint b) { return a += b; }
  modint operator-(modint a, modint b) { return a -= b; }
  modint operator*(modint a, modint b) { return a *= b; }
  modint operator^(modint a, long long n) {
    if (n == 0) return modint(1);
    modint res = (a * a) ^ (n / 2);
    if (n % 2) res = res * a;
    return res;
  }
  long long inv(long long a, long long p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
  }
  modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
  modint operator/=(modint& a, modint b) {
    a = a / b;
    return a;
  }
  const int max_n = 1 << 2;
  modint fact[max_n], factinv[max_n];
  void init_f() {
    fact[0] = modint(1);
    for (int i = 0; i < max_n - 1; i++) {
      fact[i + 1] = fact[i] * modint(i + 1);
    }
    factinv[max_n - 1] = modint(1) / fact[max_n - 1];
    for (int i = max_n - 2; i >= 0; i--) {
      factinv[i] = factinv[i + 1] * modint(i + 1);
    }
  }
  modint comb(int a, int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return fact[a] * factinv[b] * factinv[a - b];
  }
  modint combP(int a, int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return fact[a] * factinv[a - b];
  }
  int get_premitive_root(const long long& p) {
    int primitive_root = 0;
    if (!primitive_root) {
      primitive_root = [&]() {
        set<int> fac;
        int v = p - 1;
        for (long long i = 2; i * i <= v; i++)
          while (v % i == 0) fac.insert(i), v /= i;
        if (v > 1) fac.insert(v);
        for (int g = 1; g < p; g++) {
          bool ok = true;
          for (auto i : fac)
            if (mod_pow(g, (p - 1) / i, p) == 1) {
              ok = false;
              break;
            }
          if (ok) return g;
        }
        return -1;
      }();
    }
    return primitive_root;
  }
  void dft(vector<long long>& f, const long long& p, const int& proot,
           bool inverse = false) {
    int n = f.size();
    if (n == 1) return;
    vector<long long> w{1}, iw{1};
    for (int m = w.size(); m < n / 2; m *= 2) {
      long long dw = mod_pow(proot, (p - 1) / (4 * m), p),
                dwinv = mod_pow(dw, p - 2, p);
      w.resize(m * 2);
      iw.resize(m * 2);
      for (int i = 0; i < m; i++)
        w[m + i] = w[i] * dw % p, iw[m + i] = iw[i] * dwinv % p;
    }
    if (!inverse) {
      for (int m = n; m >>= 1;) {
        for (int s = 0, k = 0; s < n; s += 2 * m, k++) {
          for (int i = s; i < s + m; i++) {
            long long x = f[i], y = f[i + m] * w[k] % p;
            f[i] = x + y, f[i + m] = x - y;
            if (f[i] >= p) f[i] -= p;
            if (f[i + m] < 0) f[i + m] += p;
          }
        }
      }
    } else {
      for (int m = 1; m < n; m *= 2) {
        for (int s = 0, k = 0; s < n; s += 2 * m, k++) {
          for (int i = s; i < s + m; i++) {
            long long x = f[i], y = f[i + m];
            f[i] = x + y, f[i + m] = (x - y) * iw[k] % p;
            if (f[i] >= p) f[i] -= p;
            if (f[i + m] < 0) f[i + m] += p;
          }
        }
      }
      long long n_inv = mod_pow(n, p - 2, p);
      for (long long& v : f) (v *= n_inv) %= p;
    }
  }
  vector<long long> multi(vector<long long> g, vector<long long> h,
                          const long long& p, int n) {
    const int proot = get_premitive_root(p);
    dft(g, p, proot, false);
    dft(h, p, proot, false);
    vector<long long> f(n);
    for (int i = 0; i < n; i++) {
      f[i] = g[i] * h[i] % p;
    }
    dft(f, p, proot, true);
    return f;
  }
  constexpr long long m0 = 469762049;
  constexpr long long m1 = 167772161;
  constexpr long long m2 = 595591169;
  const long long inv01 = mod_pow(m0, m1 - 2, m1);
  const long long inv012 = mod_pow(m0 * m1, m2 - 2, m2);
  long long calc(long long& a, long long& b, long long& c, const long long& p) {
    long long res = 0;
    long long x1 = a;
    long long x2 = (b - x1) * inv01;
    x2 %= m1;
    if (x2 < 0) x2 += m1;
    long long x3 = (c - x1 - x2 * m0) % m2 * inv012;
    x3 %= m2;
    if (x3 < 0) x3 += m2;
    res = x1 + x2 * m0 % p + x3 * m0 % p * m1;
    return res % p;
  }
  vector<long long> multiply(vector<long long> g, vector<long long> h,
                             const long long& p) {
    int resz = g.size() + h.size() - 1;
    int n = 1;
    int pi = 0, qi = 0;
    for (int i = 0; i < g.size(); i++)
      if (g[i]) pi = i;
    for (int i = 0; i < h.size(); i++)
      if (h[i]) qi = i;
    int sz = pi + qi + 2;
    while (n < sz) n *= 2;
    g.resize(n);
    h.resize(n);
    vector<long long> vp[3];
    vp[0] = multi(g, h, m0, n);
    vp[1] = multi(g, h, m1, n);
    vp[2] = multi(g, h, m2, n);
    vector<long long> res(resz);
    for (int i = 0; i < res.size(); i++) {
      long long a, b, c;
      if (i < vp[0].size())
        a = vp[0][i];
      else
        a = 0;
      if (i < vp[1].size())
        b = vp[1][i];
      else
        b = 0;
      if (i < vp[2].size())
        c = vp[2][i];
      else
        c = 0;
      res[i] = calc(a, b, c, p);
    }
    return res;
  }
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> l(n), r(n);
    for (int i = 0; i < n - 1; i++) {
      l[i + 1] = (l[i] + a[i]) % k;
    }
    for (int i = 0; i < n - 1; i++) {
      r[i + 1] = (r[i] + a[n - 1 - i]) % k;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
      sum %= k;
    }
    vector<long long> f(k), g(k), h(k);
    for (int i = 0; i < n; i++) {
      f[l[i]] += 1;
      g[r[i]] += 1;
    }
    for (int c = 0; c <= m - 2; c++) {
      h[(long long)sum * c % k] += 1;
    }
    vector<long long> fg = multiply(f, g, mod);
    modint ans = 0;
    for (int i = 0; i < fg.size(); i++) {
      int id = i % k;
      int to = k - id;
      to %= k;
      ans += fg[i] * h[to];
    }
    vector<int> cnt(k);
    int obj = (long long)(m - 1) * sum % k;
    obj = k - obj;
    obj %= k;
    for (int c = n - 1; c >= 0; c--) {
      cnt[l[n - 1 - c]]++;
      int to = obj - r[c];
      if (to < 0) to += k;
      ans += cnt[to];
    }
    ans -= 1;
    fill((cnt).begin(), (cnt).end(), 0);
    for (int c = 1; c <= n - 1; c++) {
      ans += cnt[l[c]];
      cnt[l[c]] += 1;
    }
    ans *= m;
    if ((long long)sum * m % k == 0) ans += 1;
    cout << ans << "\n";
  }
  signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
  }
  