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>
  template <class p, class q>
  void umin(p& a, const q& b) {
    if (a > b) a = b;
  }
  template <class p, class q>
  void umax(p& a, const q& b) {
    if (a < b) a = b;
  }
  using ll = long long;
  using VI = std::vector<int>;
  using VLL = std::vector<ll>;
  using namespace std;
  using namespace std::chrono;
  ll n, m, k;
  int const N = 2e5 + 3;
  ll const P = 1e9 + 7;
  ll a[N];
  ll ans = 0;
  ll sum;
  ll doub[2 * N];
  ll sum_doub[2 * N];
  ll st[2][N];
  ll power(ll x, ll pw, ll mod) {
    if (!pw) return 1;
    if (pw % 2)
      return (x * power(x, pw - 1, mod)) % mod;
    else {
      ll xx = power(x, pw / 2, mod);
      return (xx * xx) % mod;
    }
  }
  void add(int t, int ind, ll val) {
    for (; ind < N; ind += (ind & (-ind))) st[t][ind] = (st[t][ind] + val) % P;
  }
  void update(int ind, ll val) {
    add(0, ind, val);
    add(0, ind + 1, P - val);
    add(1, ind, 1LL * val * (ind - 1));
    add(1, ind + 1, P - 1LL * val * ind);
  }
  ll summ(int t, int ind) {
    ll ret = 0;
    for (; ind > 0; ind -= (ind & (-ind))) ret = (ret + st[t][ind]) % P;
    return ret;
  }
  ll prefix_sum(int l) { return (summ(0, l) * l - summ(1, l) + 3 * P) % P; }
  ll query(int l, int r) {
    if (r <= k)
      return (prefix_sum(r) - prefix_sum(l - 1) + P) % P;
    else
      return (prefix_sum(k) - prefix_sum(l - 1) + prefix_sum(r - k) + P) % P;
  }
  int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = (1); i <= (n); i++) cin >> a[i];
    if (k == 1) {
      ans = 1LL * m * n;
      ans = ans % P;
      ans = (ans * (ans + P - 1)) % P;
      ans = (ans + 1) % P;
      cout << ans << "\n";
      return 0;
    }
    for (int i = (1); i <= (n); i++) sum = (sum + a[i]) % k;
    if (sum % k == 0) {
      ans += n * m * (m - 1) + 1LL;
      ans = ans % P;
    } else {
      ans += n * m * ((m - 1) / k);
      ans += 1LL * (!(m % k));
      ans = ans % P;
    }
    for (int i = (1); i <= (2 * n); i++) {
      doub[i] = a[(i - 1) % n + 1];
      sum_doub[i] = (sum_doub[i - 1] + doub[i]) % k;
    }
    ll ods = (sum % k) ? sum : 1;
    for (int i = (n + 1); i <= (2 * n - 1); i++) {
      update((sum_doub[i] * power(ods, k - 2, k)) % k + 1, 1);
    }
    ll ww = (sum_doub[2 * n] * power(ods, k - 2, k)) % k;
    if (sum % k) {
      ans = (ans + m * query(ww + 1, ww + 1 + (m - 1) % k)) % P;
      ans = (ans + ((m * ((m - 1) / k)) % P) * query(1, k)) % P;
    } else
      ans = (ans + ((m * m) % P) * query(ww + 1, ww + 1)) % P;
    for (int j = (2 * n - 1); j >= (n + 1); j--) {
      update((sum_doub[j] * power(ods, k - 2, k)) % k + 1, P - 1);
      update((sum_doub[j - n + 1] * power(ods, k - 2, k)) % k + 1, 1);
      ll ww = (sum_doub[j] * power(ods, k - 2, k)) % k;
      if (sum % k) {
        ans = (ans + m * query(ww + 1, ww + 1 + (m - 1) % k)) % P;
        ans = (ans + ((m * ((m - 1) / k)) % P) * query(1, k)) % P;
      } else
        ans = (ans + ((m * m) % P) * query(ww + 1, ww + 1)) % P;
    }
    cout << ans << "\n";
    return 0;
  }
  