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

### Prompt

Create a solution in CPP for 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;
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;
}

```