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;
  long long get_time() {
    return chrono::duration_cast<chrono::nanoseconds>(
               chrono::steady_clock::now().time_since_epoch())
        .count();
  }
  template <typename T1, typename T2>
  string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
    bool done_something = false;
    stringstream res;
    res << "[";
    for (; begin_iter != end_iter and counter; ++begin_iter) {
      done_something = true;
      counter--;
      res << *begin_iter << ", ";
    }
    string str = res.str();
    if (done_something) {
      str.pop_back();
      str.pop_back();
    }
    str += "]";
    return str;
  }
  template <typename S, typename T>
  ostream& operator<<(ostream& out, const pair<S, T>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
  }
  template <typename T>
  ostream& operator<<(ostream& out, const vector<T>& v) {
    out << "[";
    for (int i = 0; i < (int)v.size(); i++) {
      out << v[i];
      if (i != (int)v.size() - 1) out << ", ";
    }
    out << "]";
    return out;
  }
  template <class TH>
  void _dbg(const char* name, TH val) {
    clog << name << ": " << val << endl;
  }
  template <class TH, class... TA>
  void _dbg(const char* names, TH curr_val, TA... vals) {
    while (*names != ',') clog << *names++;
    clog << ": " << curr_val << ", ";
    _dbg(names + 1, vals...);
  }
  long long Inverse(long long n, long long m) {
    n %= m;
    if (n <= 1) return n;
    return m - ((m * Inverse(m, n) - 1) / n);
  }
  long long pow(long long x, long long e, long long mod) {
    long long res = 1;
    for (; e >= 1; e >>= 1) {
      if (e & 1) res = res * x % mod;
      x = x * x % mod;
    }
    return res;
  }
  struct FastMod {
    unsigned long long mod;
    unsigned long long inv;
    FastMod(unsigned long long mod) : mod(mod), inv(-1ULL / mod) {}
    unsigned long long operator()(unsigned long long x) {
      unsigned long long q = (unsigned long long)((__uint128_t(inv) * x) >> 64);
      unsigned long long r = x - q * mod;
      return r - mod * (r >= mod);
    }
  };
  struct ModularInteger {
    static int mod;
    static __uint128_t inv_mod;
    int n;
    static void set_mod(int _mod) {
      mod = _mod;
      inv_mod = -1ULL / mod;
    }
    ModularInteger() : n(0) {}
    ModularInteger(long long _n) : n(_n % mod) { n += (n < 0) * mod; }
    long long get() const { return n; }
    static int fast_mod(unsigned long long x) {
      unsigned long long q = (inv_mod * x) >> 64;
      int m = x - q * mod;
      m -= mod * (m >= mod);
      return m;
    }
    ModularInteger operator-() const { return n ? mod - n : 0; }
  };
  int ModularInteger::mod;
  __uint128_t ModularInteger::inv_mod;
  ModularInteger operator+(const ModularInteger& A, const ModularInteger& B) {
    ModularInteger C;
    C.n = A.n + B.n;
    C.n -= (C.n >= ModularInteger::mod) * ModularInteger::mod;
    return C;
  }
  void operator+=(ModularInteger& A, const ModularInteger& B) {
    A.n += B.n;
    A.n -= (A.n >= ModularInteger::mod) * ModularInteger::mod;
  }
  ModularInteger operator-(const ModularInteger& A, const ModularInteger& B) {
    ModularInteger C;
    C.n = A.n - B.n;
    C.n += (C.n < 0) * ModularInteger::mod;
    return C;
  }
  void operator-=(ModularInteger& A, const ModularInteger& B) {
    A.n -= B.n;
    A.n += (A.n < 0) * ModularInteger::mod;
  }
  ModularInteger operator*(const ModularInteger& A, const ModularInteger& B) {
    ModularInteger C;
    C.n = ModularInteger::fast_mod(((unsigned long long)A.n) * B.n);
    return C;
  }
  void operator*=(ModularInteger& A, const ModularInteger& B) {
    A.n = ModularInteger::fast_mod(((unsigned long long)A.n) * B.n);
  }
  ModularInteger operator/(const ModularInteger& A, const ModularInteger& B) {
    return A * Inverse(B.n, ModularInteger::mod);
  }
  void operator/=(ModularInteger& A, const ModularInteger& B) {
    A *= Inverse(B.n, ModularInteger::mod);
  }
  ModularInteger power(ModularInteger A, unsigned long long e) {
    ModularInteger res = 1;
    for (; e >= 1; e >>= 1) {
      if (e & 1) res *= A;
      A *= A;
    }
    return res;
  }
  bool operator==(const ModularInteger& A, const ModularInteger& B) {
    return A.n == B.n;
  }
  bool operator!=(const ModularInteger& A, const ModularInteger& B) {
    return A.n != B.n;
  }
  bool operator<(const ModularInteger& A, const ModularInteger& B) {
    return A.n < B.n;
  }
  bool operator>(const ModularInteger& A, const ModularInteger& B) {
    return A.n > B.n;
  }
  bool operator<=(const ModularInteger& A, const ModularInteger& B) {
    return A.n <= B.n;
  }
  bool operator>=(const ModularInteger& A, const ModularInteger& B) {
    return A.n >= B.n;
  }
  ostream& operator<<(ostream& out, const ModularInteger& A) {
    out << A.n;
    return out;
  }
  istream& operator>>(istream& in, ModularInteger& A) {
    long long a;
    in >> a;
    A = ModularInteger(a);
    return in;
  }
  int k;
  long long f(long long x) {
    x %= k;
    if (x < 0) x += k;
    return x;
  }
  const int MAXK = 2e5 + 10;
  long long cnt[MAXK];
  const int MAXL = 20;
  long long cnt_sum[MAXK][MAXL];
  long long cnt_clever[MAXK];
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ModularInteger::set_mod(1e9 + 7);
    int n, m;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      a[i] = f(a[i] + a[i - 1]);
    }
    long long s = a[n];
    vector<int> se(MAXL);
    se[0] = f(-s);
    for (int e = 1; e < MAXL; e++) se[e] = f(se[e - 1] * 2);
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 0; i < k; i++) cnt_sum[i][0] = cnt[i];
    for (int e = 1; e < MAXL; e++) {
      for (int i = 0; i < k; i++) {
        int j = i + se[e - 1];
        if (j >= k) j -= k;
        cnt_sum[i][e] = cnt_sum[i][e - 1] + cnt_sum[j][e - 1];
      }
    }
    for (int i = 0; i < k; i++) {
      int j = i;
      for (int e = 0; e < MAXL; e++) {
        if ((1 << e) & m) {
          cnt_clever[i] += cnt_sum[j][e];
          j += se[e];
          if (j >= k) j -= k;
        }
      }
      cnt_clever[i] -= cnt[i];
    }
    vector<int> bef(k, 0), aft(k, 0);
    for (int i = 0; i < n; i++) aft[a[i]]++;
    ModularInteger res = 0;
    for (int i = 0; i < n; i++) {
      aft[a[i]]--;
      res += aft[a[i]];
      res += bef[f(a[i] - m * s)];
      res += cnt_clever[a[i]];
      bef[a[i]]++;
    }
    res *= m;
    if (m * s % k == 0) res += 1;
    cout << res << "\n";
  }
  