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>
  #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  using namespace std;
  template <class T>
  using rque = priority_queue<T, vector<T>, greater<T>>;
  template <class T>
  bool chmin(T &a, const T &b) {
    if (b < a) {
      a = b;
      return 1;
    }
    return 0;
  }
  template <class T>
  bool chmax(T &a, const T &b) {
    if (b > a) {
      a = b;
      return 1;
    }
    return 0;
  }
  long long gcd(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    long long cnt = a % b;
    while (cnt != 0) {
      a = b;
      b = cnt;
      cnt = a % b;
    }
    return b;
  }
  long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
  }
  struct UnionFind {
    vector<long long> data;
    int num;
    UnionFind(int sz) {
      data.assign(sz, -1);
      num = sz;
    }
    bool unite(int x, int y) {
      x = find(x), y = find(y);
      if (x == y) return (false);
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
      num--;
      return (true);
    }
    int find(int k) {
      if (data[k] < 0) return (k);
      return (data[k] = find(data[k]));
    }
    long long size(int k) { return (-data[find(k)]); }
    bool same(int x, int y) { return find(x) == find(y); }
  };
  template <int mod>
  struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {
      if ((x += p.x) >= mod) x -= mod;
      return *this;
    }
    ModInt &operator-=(const ModInt &p) {
      if ((x += mod - p.x) >= mod) x -= mod;
      return *this;
    }
    ModInt &operator*=(const ModInt &p) {
      x = (int)(1LL * x * p.x % mod);
      return *this;
    }
    ModInt &operator/=(const ModInt &p) {
      *this *= p.inverse();
      return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt &operator++() { return *this += ModInt(1); }
    ModInt operator++(int) {
      ModInt tmp = *this;
      ++*this;
      return tmp;
    }
    ModInt &operator--() { return *this -= ModInt(1); }
    ModInt operator--(int) {
      ModInt tmp = *this;
      --*this;
      return tmp;
    }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {
      int a = x, b = mod, u = 1, v = 0, t;
      while (b > 0) {
        t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
      }
      return ModInt(u);
    }
    ModInt pow(int64_t n) const {
      ModInt ret(1), mul(x);
      while (n > 0) {
        if (n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
      }
      return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
    friend istream &operator>>(istream &is, ModInt &a) {
      int64_t t;
      is >> t;
      a = ModInt<mod>(t);
      return (is);
    }
    static int get_mod() { return mod; }
  };
  long long mpow2(long long x, long long n, long long mod) {
    long long ans = 1;
    while (n != 0) {
      if (n & 1) ans = ans * x % mod;
      x = x * x % mod;
      n = n >> 1;
    }
    return ans;
  }
  long long modinv2(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
  }
  template <int mod>
  struct Mod_Int {
    int x;
    Mod_Int() : x(0) {}
    Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    static int get_mod() { return mod; }
    Mod_Int &operator+=(const Mod_Int &p) {
      if ((x += p.x) >= mod) x -= mod;
      return *this;
    }
    Mod_Int &operator-=(const Mod_Int &p) {
      if ((x += mod - p.x) >= mod) x -= mod;
      return *this;
    }
    Mod_Int &operator*=(const Mod_Int &p) {
      x = (int)(1LL * x * p.x % mod);
      return *this;
    }
    Mod_Int &operator/=(const Mod_Int &p) {
      *this *= p.inverse();
      return *this;
    }
    Mod_Int &operator++() { return *this += Mod_Int(1); }
    Mod_Int operator++(int) {
      Mod_Int tmp = *this;
      ++*this;
      return tmp;
    }
    Mod_Int &operator--() { return *this -= Mod_Int(1); }
    Mod_Int operator--(int) {
      Mod_Int tmp = *this;
      --*this;
      return tmp;
    }
    Mod_Int operator-() const { return Mod_Int(-x); }
    Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }
    Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }
    Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }
    Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }
    bool operator==(const Mod_Int &p) const { return x == p.x; }
    bool operator!=(const Mod_Int &p) const { return x != p.x; }
    Mod_Int inverse() const {
      assert(*this != Mod_Int(0));
      return pow(mod - 2);
    }
    Mod_Int pow(long long k) const {
      Mod_Int now = *this, ret = 1;
      for (; k > 0; k >>= 1, now *= now) {
        if (k & 1) ret *= now;
      }
      return ret;
    }
    friend ostream &operator<<(ostream &os, const Mod_Int &p) {
      return os << p.x;
    }
    friend istream &operator>>(istream &is, Mod_Int &p) {
      long long a;
      is >> a;
      p = Mod_Int<mod>(a);
      return is;
    }
  };
  constexpr int mod = 1000000007;
  using mint = Mod_Int<mod>;
  mint mpow(mint x, long long n) {
    mint ans = 1;
    while (n != 0) {
      if (n & 1) ans *= x;
      x *= x;
      n = n >> 1;
    }
    return ans;
  }
  template <typename T>
  struct Number_Theoretic_Transform {
    static int max_base;
    static T root;
    static vector<T> r, ir;
    Number_Theoretic_Transform() {}
    static void init() {
      if (!r.empty()) return;
      int mod = T::get_mod();
      int tmp = mod - 1;
      root = 2;
      while (root.pow(tmp >> 1) == 1) root++;
      max_base = 0;
      while (tmp % 2 == 0) tmp >>= 1, max_base++;
      r.resize(max_base), ir.resize(max_base);
      for (int i = 0; i < max_base; i++) {
        r[i] = -root.pow((mod - 1) >> (i + 2));
        ir[i] = r[i].inverse();
      }
    }
    static void ntt(vector<T> &a) {
      init();
      int n = a.size();
      assert((n & (n - 1)) == 0);
      assert(n <= (1 << max_base));
      for (int k = n; k >>= 1;) {
        T w = 1;
        for (int s = 0, t = 0; s < n; s += 2 * k) {
          for (int i = s, j = s + k; i < s + k; i++, j++) {
            T x = a[i], y = w * a[j];
            a[i] = x + y, a[j] = x - y;
          }
          w *= r[__builtin_ctz(++t)];
        }
      }
    }
    static void intt(vector<T> &a) {
      init();
      int n = a.size();
      assert((n & (n - 1)) == 0);
      assert(n <= (1 << max_base));
      for (int k = 1; k < n; k <<= 1) {
        T w = 1;
        for (int s = 0, t = 0; s < n; s += 2 * k) {
          for (int i = s, j = s + k; i < s + k; i++, j++) {
            T x = a[i], y = a[j];
            a[i] = x + y, a[j] = w * (x - y);
          }
          w *= ir[__builtin_ctz(++t)];
        }
      }
      T inv = T(n).inverse();
      for (auto &e : a) e *= inv;
    }
    static vector<T> convolve(vector<T> a, vector<T> b) {
      int k = (int)a.size() + (int)b.size() - 1, n = 1;
      while (n < k) n <<= 1;
      a.resize(n), b.resize(n);
      ntt(a), ntt(b);
      for (int i = 0; i < n; i++) a[i] *= b[i];
      intt(a), a.resize(k);
      return a;
    }
  };
  template <typename T>
  int Number_Theoretic_Transform<T>::max_base = 0;
  template <typename T>
  T Number_Theoretic_Transform<T>::root = T();
  template <typename T>
  vector<T> Number_Theoretic_Transform<T>::r = vector<T>();
  template <typename T>
  vector<T> Number_Theoretic_Transform<T>::ir = vector<T>();
  const int m1 = 1045430273;
  const int m2 = 1051721729;
  const int m3 = 1053818881;
  template <typename T>
  struct Arbitrary_Mod_Number_Theoretic_Transform {
    using mint_1 = Mod_Int<m1>;
    using mint_2 = Mod_Int<m2>;
    using mint_3 = Mod_Int<m3>;
    using NTT_1 = Number_Theoretic_Transform<mint_1>;
    using NTT_2 = Number_Theoretic_Transform<mint_2>;
    using NTT_3 = Number_Theoretic_Transform<mint_3>;
    Arbitrary_Mod_Number_Theoretic_Transform() {}
    static vector<T> convolve(const vector<T> &a, const vector<T> &b) {
      int n = a.size(), m = b.size();
      vector<mint_1> a1(n), b1(m);
      vector<mint_2> a2(n), b2(m);
      vector<mint_3> a3(n), b3(m);
      for (int i = 0; i < n; i++) a1[i] = a[i].x, a2[i] = a[i].x, a3[i] = a[i].x;
      for (int i = 0; i < m; i++) b1[i] = b[i].x, b2[i] = b[i].x, b3[i] = b[i].x;
      auto x = NTT_1::convolve(a1, b1);
      auto y = NTT_2::convolve(a2, b2);
      auto z = NTT_3::convolve(a3, b3);
      const auto m1_inv_m2 = mint_2(m1).inverse().x;
      const auto m1m2_inv_m3 = (mint_3(m1) * m2).inverse().x;
      const auto m1m2_mod = (T(m1) * m2).x;
      vector<T> ret(n + m - 1);
      for (int i = 0; i < n + m - 1; i++) {
        auto v1 = ((mint_2(y[i]) + m2 - x[i].x) * m1_inv_m2).x;
        auto v2 = ((z[i] + m3 - x[i].x - mint_3(m1) * v1) * m1m2_inv_m3).x;
        ret[i] = (T(x[i].x)) + T(m1) * v1 + T(m1m2_mod) * v2;
      }
      return ret;
    }
  };
  using NTT = Arbitrary_Mod_Number_Theoretic_Transform<mint>;
  int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);
    long long n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n);
    for (long long i = 0; i < (n); i++) cin >> a[i];
    vector<long long> s(n + 1, 0);
    for (long long i = 0; i < (n); i++) s[i + 1] = (s[i] + a[i]) % k;
    vector<mint> c0(k, 0), c2(k, 0);
    for (long long i = 0; i < (n + 1); i++) c0[s[i]]++;
    mint ans = 0;
    for (long long i = 0; i < (k); i++) ans += c0[i] * (c0[i] - 1) / 2;
    c0[s[0]]--;
    long long tmp = 0;
    for (long long i = 0; i < (m - 1); i++) tmp += s[n], tmp %= k, c2[tmp]++;
    auto res = NTT::convolve(c0, c2);
    for (long long i = 0; i < (n); i++) {
      ans += res[s[i]];
      if (s[i] + k < res.size()) ans += res[s[i] + k];
    }
    long long all = s[n] * m % k;
    vector<mint> cnt(k, 0);
    for (long long i = 1; i < (n); i++) ans += cnt[s[i]], cnt[(all + s[i]) % k]++;
    ans *= m;
    if (all == 0) ans -= m - 1;
    cout << ans << endl;
  }
  