#include <bits/stdc++.h>
using namespace std;
struct cp {
  double x, y;
  cp(double a = 0, double b = 0) { x = a, y = b; }
  inline cp operator+(cp &a) { return cp{x + a.x, y + a.y}; }
  inline cp operator-(cp &a) { return cp{x - a.x, y - a.y}; }
  inline cp operator*(cp &a) {
    return cp{x * a.x - y * a.y, x * a.y + y * a.x};
  }
  inline void operator/=(double a) { x /= a, y /= a; }
  inline void operator+=(cp &a) { x += a.x, y += a.y; }
  inline cp conj() { return cp(x, -y); }
};
const double PI = acos(-1.0);
const int maxn = 800005;
void fft(vector<cp> &a, int n, int f = 0) {
  vector<cp> w(n);
  for (int i = 0, j = 0; i < n; ++i) {
    if (i > j) swap(a[i], a[j]);
    for (int l = n >> 1; (j ^= l) < l; l >>= 1)
      ;
  }
  w[0] = cp(1, 0);
  for (int l = 2; l <= n; l <<= 1) {
    cp g = cp(cos(2 * PI / l), sin(2 * PI / l));
    if (f) g = g.conj();
    for (int j = (l >> 1); j >= 0; j -= 2) w[j] = w[j >> 1];
    for (int j = 1; j < (l >> 1); j += 2) w[j] = w[j - 1] * g;
    int m = l / 2;
    for (int j = 0; j != n; j += l) {
      for (int i = 0; i < m; ++i) {
        cp tmp = w[i] * a[j + i + m];
        a[j + i + m] = a[i + j] - tmp, a[i + j] = a[i + j] + tmp;
      }
    }
  }
  if (f)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
const int mod = 1e9 + 7;
void mul(vector<long long> &a, vector<long long> &b) {
  if (max(a.size(), b.size()) < 128) {
    int sza = a.size(), szb = b.size(), len = sza + szb - 1;
    vector<long long> ret(len);
    for (int i = 0; i < sza; i++)
      for (int j = 0; j < szb; j++) ret[i + j] += a[i] * b[j] % mod;
    a.resize(len);
    for (int i = 0; i < len; ++i) a[i] = ret[i] % mod;
    while (len > 0 && !a[len - 1]) --len;
    a.resize(len);
    return;
  }
  int m = a.size() + b.size(), len = 1;
  for (; len <= m; len <<= 1)
    ;
  vector<cp> A(a.begin(), a.end()), B(b.begin(), b.end());
  A.resize(len);
  B.resize(len);
  fft(A, len);
  fft(B, len);
  for (int i = 0; i < len; ++i) A[i] = A[i] * B[i];
  fft(A, len, -1);
  a.resize(len);
  for (int i = 0; i < len; ++i) a[i] = (long long)(A[i].x + 0.5) % mod;
  while (len > 0 && !a[len - 1]) --len;
  a.resize(len);
}
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  if (k == 1) {
    long long p = 1ll * n * m % mod;
    long long ans = p * (p + 1) / 2 % mod + (p - 2) * (p - 1) / 2 % mod;
    ans %= mod;
    cout << ans << '\n';
    return 0;
  }
  vector<int> a(n), pre(n + 1), suf(n + 1);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) {
    pre[i + 1] = (pre[i] + a[i]) % k;
  }
  for (int i = n - 1; i >= 0; --i) {
    suf[i] = (suf[i + 1] + a[i]) % k;
  }
  int sum = pre[n];
  vector<long long> b(k), c(k);
  for (int i = 1; i <= n; ++i) {
    b[pre[i]] += 1;
  }
  for (int i = 0; i <= n - 1; ++i) {
    c[suf[i]] += 1;
  }
  mul(b, c);
  for (int i = k; i < b.size(); ++i) {
    (b[i % k] += b[i]) %= mod;
  }
  b.resize(k);
  auto solve1 = [&](int x) {
    vector<int> cnt(k);
    long long ret = 0;
    for (int i = 0; i <= n; ++i) {
      ret += cnt[(pre[i] - x + k) % k];
      cnt[pre[i]] += 1;
    }
    return ret % mod;
  };
  auto solve2 = [&](int x, int d) {
    x = (x - 1ll * (d - 1) * sum % k + k) % k;
    long long ret = b[x];
    return ret % mod;
  };
  long long ans = solve1(0) * m % mod;
  for (int i = 1; i <= m - 1; ++i) {
    ans += solve2(0, i) * (m - i) % mod;
  }
  long long r = 1ll * sum * m % k;
  ans += solve1(r) * m % mod;
  for (int i = 1; i <= m - 1; ++i) {
    ans += solve2(r, i) * (m - i) % mod;
  }
  vector<int> cnt1(k);
  for (int i = 1; i <= n; ++i) {
    cnt1[pre[i]] += 1;
  }
  ans -= cnt1[r];
  for (int i = 1; i < m; ++i) {
    ans -= cnt1[(r - 1ll * i * sum % k + k) % k];
  }
  vector<int> cnt2(k);
  for (int i = n - 1; i >= 0; --i) {
    cnt2[suf[i]] += 1;
  }
  ans -= cnt2[r];
  for (int i = 1; i < m; ++i) {
    ans -= cnt2[(r - 1ll * i * sum % k + k) % k];
  }
  ans += 1;
  ans %= mod;
  if (ans < 0) ans += mod;
  cout << ans << '\n';
}

### Prompt

Generate a CPP solution 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;
struct cp {
  double x, y;
  cp(double a = 0, double b = 0) { x = a, y = b; }
  inline cp operator+(cp &a) { return cp{x + a.x, y + a.y}; }
  inline cp operator-(cp &a) { return cp{x - a.x, y - a.y}; }
  inline cp operator*(cp &a) {
    return cp{x * a.x - y * a.y, x * a.y + y * a.x};
  }
  inline void operator/=(double a) { x /= a, y /= a; }
  inline void operator+=(cp &a) { x += a.x, y += a.y; }
  inline cp conj() { return cp(x, -y); }
};
const double PI = acos(-1.0);
const int maxn = 800005;
void fft(vector<cp> &a, int n, int f = 0) {
  vector<cp> w(n);
  for (int i = 0, j = 0; i < n; ++i) {
    if (i > j) swap(a[i], a[j]);
    for (int l = n >> 1; (j ^= l) < l; l >>= 1)
      ;
  }
  w[0] = cp(1, 0);
  for (int l = 2; l <= n; l <<= 1) {
    cp g = cp(cos(2 * PI / l), sin(2 * PI / l));
    if (f) g = g.conj();
    for (int j = (l >> 1); j >= 0; j -= 2) w[j] = w[j >> 1];
    for (int j = 1; j < (l >> 1); j += 2) w[j] = w[j - 1] * g;
    int m = l / 2;
    for (int j = 0; j != n; j += l) {
      for (int i = 0; i < m; ++i) {
        cp tmp = w[i] * a[j + i + m];
        a[j + i + m] = a[i + j] - tmp, a[i + j] = a[i + j] + tmp;
      }
    }
  }
  if (f)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
const int mod = 1e9 + 7;
void mul(vector<long long> &a, vector<long long> &b) {
  if (max(a.size(), b.size()) < 128) {
    int sza = a.size(), szb = b.size(), len = sza + szb - 1;
    vector<long long> ret(len);
    for (int i = 0; i < sza; i++)
      for (int j = 0; j < szb; j++) ret[i + j] += a[i] * b[j] % mod;
    a.resize(len);
    for (int i = 0; i < len; ++i) a[i] = ret[i] % mod;
    while (len > 0 && !a[len - 1]) --len;
    a.resize(len);
    return;
  }
  int m = a.size() + b.size(), len = 1;
  for (; len <= m; len <<= 1)
    ;
  vector<cp> A(a.begin(), a.end()), B(b.begin(), b.end());
  A.resize(len);
  B.resize(len);
  fft(A, len);
  fft(B, len);
  for (int i = 0; i < len; ++i) A[i] = A[i] * B[i];
  fft(A, len, -1);
  a.resize(len);
  for (int i = 0; i < len; ++i) a[i] = (long long)(A[i].x + 0.5) % mod;
  while (len > 0 && !a[len - 1]) --len;
  a.resize(len);
}
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  if (k == 1) {
    long long p = 1ll * n * m % mod;
    long long ans = p * (p + 1) / 2 % mod + (p - 2) * (p - 1) / 2 % mod;
    ans %= mod;
    cout << ans << '\n';
    return 0;
  }
  vector<int> a(n), pre(n + 1), suf(n + 1);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) {
    pre[i + 1] = (pre[i] + a[i]) % k;
  }
  for (int i = n - 1; i >= 0; --i) {
    suf[i] = (suf[i + 1] + a[i]) % k;
  }
  int sum = pre[n];
  vector<long long> b(k), c(k);
  for (int i = 1; i <= n; ++i) {
    b[pre[i]] += 1;
  }
  for (int i = 0; i <= n - 1; ++i) {
    c[suf[i]] += 1;
  }
  mul(b, c);
  for (int i = k; i < b.size(); ++i) {
    (b[i % k] += b[i]) %= mod;
  }
  b.resize(k);
  auto solve1 = [&](int x) {
    vector<int> cnt(k);
    long long ret = 0;
    for (int i = 0; i <= n; ++i) {
      ret += cnt[(pre[i] - x + k) % k];
      cnt[pre[i]] += 1;
    }
    return ret % mod;
  };
  auto solve2 = [&](int x, int d) {
    x = (x - 1ll * (d - 1) * sum % k + k) % k;
    long long ret = b[x];
    return ret % mod;
  };
  long long ans = solve1(0) * m % mod;
  for (int i = 1; i <= m - 1; ++i) {
    ans += solve2(0, i) * (m - i) % mod;
  }
  long long r = 1ll * sum * m % k;
  ans += solve1(r) * m % mod;
  for (int i = 1; i <= m - 1; ++i) {
    ans += solve2(r, i) * (m - i) % mod;
  }
  vector<int> cnt1(k);
  for (int i = 1; i <= n; ++i) {
    cnt1[pre[i]] += 1;
  }
  ans -= cnt1[r];
  for (int i = 1; i < m; ++i) {
    ans -= cnt1[(r - 1ll * i * sum % k + k) % k];
  }
  vector<int> cnt2(k);
  for (int i = n - 1; i >= 0; --i) {
    cnt2[suf[i]] += 1;
  }
  ans -= cnt2[r];
  for (int i = 1; i < m; ++i) {
    ans -= cnt2[(r - 1ll * i * sum % k + k) % k];
  }
  ans += 1;
  ans %= mod;
  if (ans < 0) ans += mod;
  cout << ans << '\n';
}

```