#include <bits/stdc++.h>
using namespace std;
const int maxn = 524288, P = 1000000007;
const double PI = acos(-1);
int n, m, K, ans, a[maxn], pre[maxn], suf[maxn];
int c[maxn], cl[maxn], cr[maxn], cur[maxn];
int lim, l, r[maxn];
complex<double> A[maxn], B[maxn];
void DFT(complex<double> *c, int type) {
  for (int i = 0; i < lim; i++) {
    if (i < r[i]) swap(c[i], c[r[i]]);
  }
  for (int i = 1; i < lim; i <<= 1) {
    complex<double> x(cos(PI / i), type * sin(PI / i));
    for (int j = 0; j < lim; j += i << 1) {
      complex<double> y(1, 0);
      for (int k = 0; k < i; k++, y *= x) {
        complex<double> p = c[j + k], q = y * c[i + j + k];
        c[j + k] = p + q, c[i + j + k] = p - q;
      }
    }
  }
  if (type == -1) {
    for (int i = 0; i < lim; i++) c[i] /= lim;
  }
}
int main() {
  scanf("%d %d %d", &n, &m, &K);
  int all = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]), (all += a[i]) %= K;
    pre[i] = (pre[i - 1] + a[i]) % K;
    if (i < n) cl[pre[i]]++, A[pre[i]] += 1;
  }
  for (int i = n; i; i--) {
    suf[i] = (suf[i + 1] + a[i]) % K;
    if (i > 1) cr[suf[i]]++, B[suf[i]] += 1;
  }
  for (lim = 1; lim < K << 1; lim <<= 1) l++;
  for (int i = 0; i < lim; i++) {
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  }
  DFT(A, 1), DFT(B, 1);
  for (int i = 0; i < lim; i++) {
    A[i] *= B[i];
  }
  DFT(A, -1);
  for (int i = 0; i < K + K; i++) {
    c[i % K] = (c[i % K] + (long long)round(A[i].real())) % P;
  }
  int all_m = 1LL * m * all % K;
  auto solve = [&](int r, int type) {
    memset(cur, 0, sizeof(cur));
    int num = 0;
    for (int i = 0; i <= n; i++) {
      (num += cur[(pre[i] - r + K) % K]) %= P;
      cur[pre[i]]++;
    }
    if (all == r) (num += P - 1) %= P;
    ans = (ans + 1LL * m * num) % P;
    for (int i = 0; i <= m; i++) {
      int tar = (r - 1LL * i * all % K + K) % K;
      if (i < m) ans = (ans + 1LL * c[tar] * (m - i - 1)) % P;
      if (i) {
        if (!tar) (ans += m - i + 1) %= P;
        ans = (ans + 1LL * (cl[tar] + cr[tar]) * (m - i)) % P;
      }
    }
    if (type) {
      for (int i = 0; i < m; i++) {
        int tar = (r - 1LL * i * all % K + K) % K;
        if (i && !tar) (ans += P - 1) %= P, (ans += P - 1) %= P;
        ans = (ans - cl[tar] + P) % P;
        ans = (ans - cr[tar] + P) % P;
      }
      if (all_m == r) (ans += P - 1) %= P;
    }
  };
  solve(0, 0), solve(all_m, 1);
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

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>
using namespace std;
const int maxn = 524288, P = 1000000007;
const double PI = acos(-1);
int n, m, K, ans, a[maxn], pre[maxn], suf[maxn];
int c[maxn], cl[maxn], cr[maxn], cur[maxn];
int lim, l, r[maxn];
complex<double> A[maxn], B[maxn];
void DFT(complex<double> *c, int type) {
  for (int i = 0; i < lim; i++) {
    if (i < r[i]) swap(c[i], c[r[i]]);
  }
  for (int i = 1; i < lim; i <<= 1) {
    complex<double> x(cos(PI / i), type * sin(PI / i));
    for (int j = 0; j < lim; j += i << 1) {
      complex<double> y(1, 0);
      for (int k = 0; k < i; k++, y *= x) {
        complex<double> p = c[j + k], q = y * c[i + j + k];
        c[j + k] = p + q, c[i + j + k] = p - q;
      }
    }
  }
  if (type == -1) {
    for (int i = 0; i < lim; i++) c[i] /= lim;
  }
}
int main() {
  scanf("%d %d %d", &n, &m, &K);
  int all = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]), (all += a[i]) %= K;
    pre[i] = (pre[i - 1] + a[i]) % K;
    if (i < n) cl[pre[i]]++, A[pre[i]] += 1;
  }
  for (int i = n; i; i--) {
    suf[i] = (suf[i + 1] + a[i]) % K;
    if (i > 1) cr[suf[i]]++, B[suf[i]] += 1;
  }
  for (lim = 1; lim < K << 1; lim <<= 1) l++;
  for (int i = 0; i < lim; i++) {
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  }
  DFT(A, 1), DFT(B, 1);
  for (int i = 0; i < lim; i++) {
    A[i] *= B[i];
  }
  DFT(A, -1);
  for (int i = 0; i < K + K; i++) {
    c[i % K] = (c[i % K] + (long long)round(A[i].real())) % P;
  }
  int all_m = 1LL * m * all % K;
  auto solve = [&](int r, int type) {
    memset(cur, 0, sizeof(cur));
    int num = 0;
    for (int i = 0; i <= n; i++) {
      (num += cur[(pre[i] - r + K) % K]) %= P;
      cur[pre[i]]++;
    }
    if (all == r) (num += P - 1) %= P;
    ans = (ans + 1LL * m * num) % P;
    for (int i = 0; i <= m; i++) {
      int tar = (r - 1LL * i * all % K + K) % K;
      if (i < m) ans = (ans + 1LL * c[tar] * (m - i - 1)) % P;
      if (i) {
        if (!tar) (ans += m - i + 1) %= P;
        ans = (ans + 1LL * (cl[tar] + cr[tar]) * (m - i)) % P;
      }
    }
    if (type) {
      for (int i = 0; i < m; i++) {
        int tar = (r - 1LL * i * all % K + K) % K;
        if (i && !tar) (ans += P - 1) %= P, (ans += P - 1) %= P;
        ans = (ans - cl[tar] + P) % P;
        ans = (ans - cr[tar] + P) % P;
      }
      if (all_m == r) (ans += P - 1) %= P;
    }
  };
  solve(0, 0), solve(all_m, 1);
  printf("%d\n", ans);
  return 0;
}

```