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;
  const ll mod = 77309411329ll;
  const ll modinv2 = (mod + 1) / 2;
  const ll G = 7;
  const int maxn = (1 << 19) + 5;
  inline ll add(ll a, ll b) { return a + b >= mod ? a + b - mod : a + b; }
  inline void inc(ll& a, ll b) {
    if ((a += b) >= mod) a -= mod;
  }
  inline ll sub(ll a, ll b) { return a - b < 0 ? a - b + mod : a - b; }
  inline void dec(ll& a, ll b) {
    if ((a -= b) < 0) a += mod;
  }
  inline ll mul(ll a, ll b) {
    return (a * b - (ll)((long double)a / mod * b) * mod + mod) % mod;
  }
  inline ll qpow(ll x, ll n) {
    ll ans = 1;
    for (; n; n >>= 1, x = mul(x, x))
      if (n & 1) ans = mul(ans, x);
    return ans;
  }
  ll wn[30], iwn[30];
  inline void init() {
    wn[21] = qpow(G, (mod - 1) / (1 << 21));
    for (int i = 20; i >= 0; i--) wn[i] = mul(wn[i + 1], wn[i + 1]);
    iwn[21] = qpow(wn[21], (1 << 21) - 1);
    for (int i = 20; i >= 0; i--) iwn[i] = mul(iwn[i + 1], iwn[i + 1]);
  }
  inline void revbin_permute(ll a[], int n) {
    int i = 1, j = n >> 1, k;
    for (; i < n - 1; i++) {
      if (i < j) swap(a[i], a[j]);
      for (k = n >> 1; j >= k;) {
        j -= k;
        k >>= 1;
      }
      if (j < k) j += k;
    }
  }
  void NTT(ll f[], int ldn, int is) {
    int n = (1 << ldn);
    revbin_permute(f, n);
    for (int i = 0; i < n; i += 2) {
      ll tmp1 = f[i], tmp2 = f[i + 1];
      f[i] = add(tmp1, tmp2), f[i + 1] = sub(tmp1, tmp2);
    }
    for (int ldm = 2; ldm <= ldn; ldm++) {
      int m = (1 << ldm), mh = (m >> 1);
      ll dw = is > 0 ? wn[ldm] : iwn[ldm], w = 1;
      for (int j = 0; j < mh; j++) {
        for (int r = 0; r < n; r += m) {
          ll u = f[r + j], v = mul(f[r + j + mh], w);
          f[r + j] = add(u, v);
          f[r + j + mh] = sub(u, v);
        }
        w = mul(w, dw);
      }
    }
  }
  void convolution(ll f[], ll g[], int n) {
    int ldn;
    for (int i = 20; i >= 0; i--)
      if (n & (1 << i)) {
        ldn = i;
        break;
      }
    NTT(f, ldn, 1);
    NTT(g, ldn, 1);
    for (int i = 0; i < n; i++) f[i] = mul(f[i], g[i]);
    NTT(f, ldn, -1);
    ll iv = qpow(n, mod - 2);
    for (int i = 0; i < n; i++) f[i] = mul(f[i], iv);
  }
  const int M = 1000000007;
  int a[maxn];
  ll f[maxn], g[maxn];
  int main(void) {
    init();
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) a[i] = (a[i] + a[i - 1]) % k;
    ll ans = 0;
    map<int, int> cnt;
    ++cnt[a[0]];
    for (int i = 1; i <= n; i++) {
      ans = (ans + cnt[a[i]]) % M;
      if (i < n) {
        ans = (ans + cnt[(a[i] - m * (ll)a[n] % k + k) % k]) % M;
        if ((a[i] - m * (ll)a[n] % k + k) % k == a[0]) ans--;
      }
      ++cnt[a[i]];
    }
    for (int i = 0; i < n; i++) f[a[i]]++;
    for (int i = 1; i <= n; i++) g[(k - a[i]) % k]++;
    int len = 2;
    while (len < 2 * k) len *= 2;
    convolution(f, g, len);
    for (int i = k; i < len; i++) f[i % k] += f[i];
    for (int i = 1; i <= m - 1; i++) ans = (ans + f[i * (ll)a[n] % k]) % M;
    ans = ans * m % M;
    if (a[n] * (ll)m % k == 0) ans -= m - 1;
    printf("%lld\n", ans);
    return 0;
  }
  