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;
  using ull = unsigned long long;
  const int N = 2e6 + 100;
  const int MOD = 1e9 + 7;
  const double pi = acos(-1.0);
  struct base {
    double a, b;
    base() {}
    base(double x) : a(x), b(0) {}
    base(double x, double y) : a(x), b(y) {}
    friend base operator+(const base& a, const base& b) {
      return base(a.a + b.a, a.b + b.b);
    }
    friend base operator-(const base& a, const base& b) {
      return base(a.a - b.a, a.b - b.b);
    }
    friend base operator*(const base& a, const base& b) {
      return base(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
    }
    friend base operator/(const base& a, double b) {
      return base(a.a / b, a.b / b);
    }
  };
  int a[N], pref[N], suff[N], blocks[N];
  ll res[N];
  base b[N];
  void fft(base* a, int n, bool inv) {
    for (int i = 1, j = 0; i < n; ++i) {
      int bit = n / 2;
      for (; j >= bit; bit /= 2) {
        j -= bit;
      }
      j += bit;
      if (i < j) {
        swap(a[i], a[j]);
      }
    }
    for (int len = 2; len <= n; len *= 2) {
      double ang = 2 * pi / len * (inv ? -1 : 1);
      base wlen(cos(ang), sin(ang));
      for (int i = 0; i < n; i += len) {
        base w(1);
        for (int j = 0; j < len / 2; ++j) {
          base u = a[i + j], v = a[i + j + len / 2] * w;
          a[i + j] = u + v;
          a[i + j + len / 2] = u - v;
          w = w * wlen;
        }
      }
    }
    if (inv) {
      for (int i = 0; i < n; ++i) {
        a[i] = a[i] / n;
      }
    }
  }
  void multiply(int* fa, int* fb, ll* fc, int k) {
    int n = 1;
    while (n < k) {
      n *= 2;
    }
    n *= 2;
    for (int i = 0; i < n; ++i) {
      if (i < k) {
        b[i].a = fa[i];
        b[i].b = fb[i];
      } else {
        b[i] = base(0);
      }
    }
    fft(b, n, false);
    for (int i = 0; i < n; ++i) {
      b[i] = b[i] * b[i];
    }
    fft(b, n, true);
    for (int i = 0; i < k; ++i) {
      fc[i] = (ll(b[i].b + 0.5) + ll(b[i + k].b + 0.5)) / 2;
    }
  }
  void solve() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; ++i) {
      scanf("%d", a + i);
      a[i] %= k;
    }
    int ans = 0;
    if (m >= 2) {
      int cur_suff = 0;
      for (int i = n - 1; i >= 0; --i) {
        cur_suff += a[i];
        if (cur_suff >= k) {
          cur_suff -= k;
        }
        ++suff[cur_suff];
      }
      int cur_blocks = 0;
      for (int i = 0; i <= m - 2; ++i) {
        ++blocks[cur_blocks];
        cur_blocks += cur_suff;
        if (cur_blocks >= k) {
          cur_blocks -= k;
        }
      }
      multiply(suff, blocks, res, k);
      int pref = 0;
      for (int r = 0; r < n; ++r) {
        pref += a[r];
        if (pref >= k) {
          pref -= k;
        }
        int x = (pref == 0 ? 0 : k - pref);
        ans = (ans + res[x]) % MOD;
      }
    }
    ++pref[0];
    int cur_pref = 0;
    for (int r = 0; r < n; ++r) {
      cur_pref += a[r];
      if (cur_pref >= k) {
        cur_pref -= k;
      }
      ans = (ans + pref[cur_pref]) % MOD;
      ++pref[cur_pref];
    }
    int blocks = (ll(cur_pref) * (m - 1)) % k;
    int full = (ll(cur_pref) * m) % k;
    int cur_suff = 0;
    for (int i = 0; i < k; ++i) {
      suff[i] = 0;
    }
    for (int i = n - 1; i >= 0; --i) {
      int val = cur_pref + blocks;
      if (val >= k) {
        val -= k;
      }
      val = (val == 0 ? 0 : k - val);
      ans = (ans + suff[val]) % MOD;
      cur_suff += a[i];
      if (cur_suff >= k) {
        cur_suff -= k;
      }
      ++suff[cur_suff];
      cur_pref -= a[i];
      if (cur_pref < 0) {
        cur_pref += k;
      }
    }
    if (full == 0 && m >= 2) {
      --ans;
      if (ans < 0) {
        ans += MOD;
      }
    }
    if (full == 0 && m == 1) {
      --ans;
      if (ans < 0) {
        ans += MOD;
      }
    }
    if (full == 0) {
      ans -= n - 1;
      if (ans < 0) {
        ans += MOD;
      }
    }
    ans = (ll(ans) * m) % MOD;
    if (full == 0) {
      ++ans;
      if (ans >= MOD) {
        ans -= MOD;
      }
    }
    printf("%d\n", ans);
  }
  int main() {
    int t = 1;
    for (int i = 0; i < t; ++i) {
      solve();
    }
    return 0;
  }
  