#include <bits/stdc++.h>
using namespace std;
struct comp {
  double a, b;
  comp() {}
  comp(double x) : a(x), b(0) {}
  comp(double x, double y) : a(x), b(y) {}
};
inline comp operator+(comp a, comp b) { return comp(a.a + b.a, a.b + b.b); }
inline comp operator-(comp a, comp b) { return comp(a.a - b.a, a.b - b.b); }
inline comp operator*(comp a, comp b) {
  return comp(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
}
ostream& operator<<(ostream& a, comp b) {
  a << "(" << b.a << "," << b.b << ")";
  return a;
}
int K;
comp w[2][1234567];
comp qp(comp a, long long b) {
  comp x = 1;
  while (b) {
    if (b & 1) x = x * a;
    a = a * a;
    b >>= 1;
  }
  return x;
}
long long qp(long long a, long long b, int MOD) {
  long long x = 1;
  a %= MOD;
  while (b) {
    if (b & 1) x = x * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return x;
}
const double pi = acos(-1);
int rev[1234567];
void init(int s) {
  for (K = 1; K < s; K <<= 1)
    ;
  {
    double t = pi * 2 / K;
    for (int i = 0; i <= K; ++i) w[0][i] = comp(cos(t * i), sin(t * i));
  }
  for (int i = 0; i <= K; ++i) w[1][i] = w[0][K - i];
  for (int i = 0; i < K; ++i) {
    int t = 0, x = i;
    for (int j = 1; j < K; j <<= 1) t = t * 2 + (x & 1), x >>= 1;
    rev[i] = t;
  }
}
void fft(comp* x, int k) {
  for (int i = 0; i < K; ++i)
    if (i < rev[i]) swap(x[i], x[rev[i]]);
  for (int i = 2; i <= K; i <<= 1)
    for (int j = 0; j < K; j += i)
      for (int s = 0; s < (i >> 1); ++s) {
        comp t = x[j + s + (i >> 1)] * w[k][K / i * s];
        x[j + s + (i >> 1)] = x[j + s] - t;
        x[j + s] = x[j + s] + t;
      }
  if (k) return;
  double sK = sqrt(K);
  for (int i = 0; i < K; ++i) x[i].a /= sK, x[i].b /= sK;
}
int a0_[1234567], b0_[1234567], a1_[1234567], b1_[1234567];
long long x0_[1234567], x1_[1234567];
comp a0[1234567], b0[1234567], a1[1234567], b1[1234567], x0[1234567],
    x1[1234567], x2[1234567];
comp ps[1234567];
template <class T>
void comb_fft0(T* a, T* b, comp* aa, comp* bb) {
  for (int i = 0; i < K; ++i) ps[i].a = a[i], ps[i].b = b[i];
  fft(ps, 0);
  for (int i = 0; i < K; ++i) {
    comp pr = ps[i ? (K - i) : i];
    pr.b = -pr.b;
    aa[i] = (ps[i] + pr) * 0.5;
    bb[i] = (ps[i] - pr) * 0.5;
    swap(bb[i].a, bb[i].b);
    bb[i].b = -bb[i].b;
  }
}
template <class T>
void comb_fft1(comp* aa, comp* bb, T* a, T* b) {
  for (int i = 0; i < K; ++i) {
    comp t = bb[i];
    t.b *= -1;
    swap(t.a, t.b);
    ps[i] = aa[i] + t;
  }
  fft(ps, 1);
  for (int i = 0; i < K; ++i) a[i] = llround(ps[i].a), b[i] = llround(ps[i].b);
}
vector<int> conv(const vector<int>& a, const vector<int>& b, int p) {
  if (a.size() && b.size())
    ;
  else
    return vector<int>();
  init(a.size() + b.size() + 2);
  for (int i = 0; i < K; ++i) a0_[i] = a1_[i] = b0_[i] = b1_[i] = 0;
  for (int i = 0; i < (int)a.size(); ++i) {
    int t = (a[i] % p + p) % p;
    a0_[i] = t % 32768, a1_[i] = t / 32768;
  }
  for (int i = 0; i < (int)b.size(); ++i) {
    int t = (b[i] % p + p) % p;
    b0_[i] = t % 32768, b1_[i] = t / 32768;
  }
  comb_fft0(a0_, a1_, a0, a1);
  comb_fft0(b0_, b1_, b0, b1);
  for (int i = 0; i < K; ++i)
    x0[i] = a0[i] * b0[i], x1[i] = a0[i] * b1[i] + a1[i] * b0[i],
    x2[i] = a1[i] * b1[i];
  comb_fft1(x0, x1, x0_, x1_);
  fft(x2, 1);
  vector<int> c;
  for (int i = 0; i < int(a.size() + b.size() - 1); ++i) {
    long long s = x0_[i] % p + x1_[i] % p * 32768 +
                  llround(x2[i].a) % p * 32768 % p * 32768;
    s = (s % p + p) % p;
    c.push_back(s);
  }
  return c;
}
int n, m, k, a[1234567], s[1234567];
long long su = 0;
const int MOD = 1e9 + 7;
int cm[1234567];
long long calc_z(int p) {
  memset(cm, 0, sizeof cm);
  long long aa = 0;
  for (int i = 0; i <= n; ++i) {
    aa += cm[(s[i] - p + k) % k];
    cm[s[i]]++;
  }
  aa %= MOD;
  aa = aa * m % MOD;
  vector<int> ss(k + 1), sb(k + 1);
  for (int i = 1; i <= n; ++i) ss[s[i]]++;
  for (int i = 0; i < n; ++i) sb[(s[n] - s[i] + k) % k]++;
  ss = conv(ss, sb, MOD);
  vector<int> oo(k + 1);
  for (int i = 0; i < ss.size(); ++i) (oo[i % k] += ss[i]) %= MOD;
  for (int u = 2; u <= m; ++u) {
    aa += oo[((p - s[n] * (long long)(u - 2)) % k + k) % k] *
          (long long)(m - u + 1) % MOD;
  }
  return aa;
}
long long calc_pre(int su) {
  vector<int> ss(k + 1);
  for (int i = 1; i <= n; ++i) {
    ss[s[i]]++;
  }
  long long aa = 0;
  for (int u = 0; u < m; ++u) {
    aa += ss[((su - s[n] * (long long)u) % k + k) % k];
    aa %= MOD;
  }
  return aa % MOD;
}
long long calc_suf(int su) {
  vector<int> ss(k + 1);
  for (int i = 0; i < n; ++i) {
    ss[(s[n] - s[i] + k) % k]++;
  }
  long long aa = 0;
  for (int u = 0; u < m; ++u) {
    aa += ss[((su - s[n] * (long long)u) % k + k) % k];
    aa %= MOD;
  }
  return aa % MOD;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) s[i] = (s[i - 1] + a[i]) % k;
  su = s[n] * (long long)m % k;
  long long ans = calc_z(0);
  ans += calc_z(su) - calc_pre(su) - calc_suf(su) + 1;
  ans %= MOD;
  ans = (ans % MOD + MOD) % MOD;
  cout << ans << "\n";
}

### Prompt

Develop a solution in cpp to the problem described below:

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 comp {
  double a, b;
  comp() {}
  comp(double x) : a(x), b(0) {}
  comp(double x, double y) : a(x), b(y) {}
};
inline comp operator+(comp a, comp b) { return comp(a.a + b.a, a.b + b.b); }
inline comp operator-(comp a, comp b) { return comp(a.a - b.a, a.b - b.b); }
inline comp operator*(comp a, comp b) {
  return comp(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
}
ostream& operator<<(ostream& a, comp b) {
  a << "(" << b.a << "," << b.b << ")";
  return a;
}
int K;
comp w[2][1234567];
comp qp(comp a, long long b) {
  comp x = 1;
  while (b) {
    if (b & 1) x = x * a;
    a = a * a;
    b >>= 1;
  }
  return x;
}
long long qp(long long a, long long b, int MOD) {
  long long x = 1;
  a %= MOD;
  while (b) {
    if (b & 1) x = x * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return x;
}
const double pi = acos(-1);
int rev[1234567];
void init(int s) {
  for (K = 1; K < s; K <<= 1)
    ;
  {
    double t = pi * 2 / K;
    for (int i = 0; i <= K; ++i) w[0][i] = comp(cos(t * i), sin(t * i));
  }
  for (int i = 0; i <= K; ++i) w[1][i] = w[0][K - i];
  for (int i = 0; i < K; ++i) {
    int t = 0, x = i;
    for (int j = 1; j < K; j <<= 1) t = t * 2 + (x & 1), x >>= 1;
    rev[i] = t;
  }
}
void fft(comp* x, int k) {
  for (int i = 0; i < K; ++i)
    if (i < rev[i]) swap(x[i], x[rev[i]]);
  for (int i = 2; i <= K; i <<= 1)
    for (int j = 0; j < K; j += i)
      for (int s = 0; s < (i >> 1); ++s) {
        comp t = x[j + s + (i >> 1)] * w[k][K / i * s];
        x[j + s + (i >> 1)] = x[j + s] - t;
        x[j + s] = x[j + s] + t;
      }
  if (k) return;
  double sK = sqrt(K);
  for (int i = 0; i < K; ++i) x[i].a /= sK, x[i].b /= sK;
}
int a0_[1234567], b0_[1234567], a1_[1234567], b1_[1234567];
long long x0_[1234567], x1_[1234567];
comp a0[1234567], b0[1234567], a1[1234567], b1[1234567], x0[1234567],
    x1[1234567], x2[1234567];
comp ps[1234567];
template <class T>
void comb_fft0(T* a, T* b, comp* aa, comp* bb) {
  for (int i = 0; i < K; ++i) ps[i].a = a[i], ps[i].b = b[i];
  fft(ps, 0);
  for (int i = 0; i < K; ++i) {
    comp pr = ps[i ? (K - i) : i];
    pr.b = -pr.b;
    aa[i] = (ps[i] + pr) * 0.5;
    bb[i] = (ps[i] - pr) * 0.5;
    swap(bb[i].a, bb[i].b);
    bb[i].b = -bb[i].b;
  }
}
template <class T>
void comb_fft1(comp* aa, comp* bb, T* a, T* b) {
  for (int i = 0; i < K; ++i) {
    comp t = bb[i];
    t.b *= -1;
    swap(t.a, t.b);
    ps[i] = aa[i] + t;
  }
  fft(ps, 1);
  for (int i = 0; i < K; ++i) a[i] = llround(ps[i].a), b[i] = llround(ps[i].b);
}
vector<int> conv(const vector<int>& a, const vector<int>& b, int p) {
  if (a.size() && b.size())
    ;
  else
    return vector<int>();
  init(a.size() + b.size() + 2);
  for (int i = 0; i < K; ++i) a0_[i] = a1_[i] = b0_[i] = b1_[i] = 0;
  for (int i = 0; i < (int)a.size(); ++i) {
    int t = (a[i] % p + p) % p;
    a0_[i] = t % 32768, a1_[i] = t / 32768;
  }
  for (int i = 0; i < (int)b.size(); ++i) {
    int t = (b[i] % p + p) % p;
    b0_[i] = t % 32768, b1_[i] = t / 32768;
  }
  comb_fft0(a0_, a1_, a0, a1);
  comb_fft0(b0_, b1_, b0, b1);
  for (int i = 0; i < K; ++i)
    x0[i] = a0[i] * b0[i], x1[i] = a0[i] * b1[i] + a1[i] * b0[i],
    x2[i] = a1[i] * b1[i];
  comb_fft1(x0, x1, x0_, x1_);
  fft(x2, 1);
  vector<int> c;
  for (int i = 0; i < int(a.size() + b.size() - 1); ++i) {
    long long s = x0_[i] % p + x1_[i] % p * 32768 +
                  llround(x2[i].a) % p * 32768 % p * 32768;
    s = (s % p + p) % p;
    c.push_back(s);
  }
  return c;
}
int n, m, k, a[1234567], s[1234567];
long long su = 0;
const int MOD = 1e9 + 7;
int cm[1234567];
long long calc_z(int p) {
  memset(cm, 0, sizeof cm);
  long long aa = 0;
  for (int i = 0; i <= n; ++i) {
    aa += cm[(s[i] - p + k) % k];
    cm[s[i]]++;
  }
  aa %= MOD;
  aa = aa * m % MOD;
  vector<int> ss(k + 1), sb(k + 1);
  for (int i = 1; i <= n; ++i) ss[s[i]]++;
  for (int i = 0; i < n; ++i) sb[(s[n] - s[i] + k) % k]++;
  ss = conv(ss, sb, MOD);
  vector<int> oo(k + 1);
  for (int i = 0; i < ss.size(); ++i) (oo[i % k] += ss[i]) %= MOD;
  for (int u = 2; u <= m; ++u) {
    aa += oo[((p - s[n] * (long long)(u - 2)) % k + k) % k] *
          (long long)(m - u + 1) % MOD;
  }
  return aa;
}
long long calc_pre(int su) {
  vector<int> ss(k + 1);
  for (int i = 1; i <= n; ++i) {
    ss[s[i]]++;
  }
  long long aa = 0;
  for (int u = 0; u < m; ++u) {
    aa += ss[((su - s[n] * (long long)u) % k + k) % k];
    aa %= MOD;
  }
  return aa % MOD;
}
long long calc_suf(int su) {
  vector<int> ss(k + 1);
  for (int i = 0; i < n; ++i) {
    ss[(s[n] - s[i] + k) % k]++;
  }
  long long aa = 0;
  for (int u = 0; u < m; ++u) {
    aa += ss[((su - s[n] * (long long)u) % k + k) % k];
    aa %= MOD;
  }
  return aa % MOD;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) s[i] = (s[i - 1] + a[i]) % k;
  su = s[n] * (long long)m % k;
  long long ans = calc_z(0);
  ans += calc_z(su) - calc_pre(su) - calc_suf(su) + 1;
  ans %= MOD;
  ans = (ans % MOD + MOD) % MOD;
  cout << ans << "\n";
}

```