#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;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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].

### Response

```cpp
#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;
}

```