#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(51);
const long long MOD = 1e9 + 7, N = 2e5 + 10;
long long t[N];
long long add(long long a, long long b) {
  return a + b >= MOD ? a + b - MOD : a + b;
}
long long sub(long long a, long long b) {
  return a - b < 0 ? a - b + MOD : a - b;
}
long long mul(long long a, long long b) { return (a * b % MOD); }
void inc(long long i, long long d) {
  for (; i < N; i = (i | (i + 1))) {
    t[i] += d;
  }
}
long long get(long long r) {
  long long ans = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    ans += t[r];
  }
  return ans;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, k;
  cin >> n >> m >> k;
  vector<long long> a(n), pr(n + 1), ind(k);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    pr[i + 1] = (pr[i] + a[i]) % k;
  }
  if (pr.back() == 0) {
    vector<long long> cnt(k);
    for (long long i = 1; i <= n; i++) {
      cnt[pr[i]] = add(cnt[pr[i]], m);
    }
    long long ans = 0;
    for (long long i = 0; i < k; i++) {
      ans = add(ans, mul(cnt[i], sub(cnt[i], 1)));
    }
    cout << add(ans, 1) << endl;
    return 0;
  }
  long long now = 0, ans = 0;
  for (long long i = 0; i < k; i++) {
    ind[now] = i;
    now = (now + pr.back()) % k;
  }
  for (long long i = n - 1; i >= 0; i--) {
    inc(ind[pr[i + 1]], 1);
    long long now = mul(get(k - 1), m / k);
    long long r = ind[pr[i]], l = r - m % k + 1;
    if (l < 0) {
      now = add(now, sub(get(k - 1), get(k + l - 1)));
      now = add(now, get(r));
    } else {
      now = add(now, sub(get(r), get(l - 1)));
    }
    ans = add(ans, mul(now, m));
  }
  for (long long i = 0; i < N; i++) t[i] = 0;
  for (long long i = 1; i < n; i++) {
    inc(ind[pr[i]], 1);
    long long now = mul(get(k - 1), m / k);
    long long r = ind[(pr[i] - pr.back() + k) % k], l = r - m % k + 1;
    if (l < 0) {
      now = add(now, sub(get(k - 1), get(k + l - 1)));
      now = add(now, get(r));
    } else {
      now = add(now, sub(get(r), get(l - 1)));
    }
    ans = add(ans, mul(now, m));
  }
  if (pr.back() * m % k == 0) {
    ans = sub(ans, mul(n, m) - 1);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
mt19937 rnd(51);
const long long MOD = 1e9 + 7, N = 2e5 + 10;
long long t[N];
long long add(long long a, long long b) {
  return a + b >= MOD ? a + b - MOD : a + b;
}
long long sub(long long a, long long b) {
  return a - b < 0 ? a - b + MOD : a - b;
}
long long mul(long long a, long long b) { return (a * b % MOD); }
void inc(long long i, long long d) {
  for (; i < N; i = (i | (i + 1))) {
    t[i] += d;
  }
}
long long get(long long r) {
  long long ans = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    ans += t[r];
  }
  return ans;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, k;
  cin >> n >> m >> k;
  vector<long long> a(n), pr(n + 1), ind(k);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    pr[i + 1] = (pr[i] + a[i]) % k;
  }
  if (pr.back() == 0) {
    vector<long long> cnt(k);
    for (long long i = 1; i <= n; i++) {
      cnt[pr[i]] = add(cnt[pr[i]], m);
    }
    long long ans = 0;
    for (long long i = 0; i < k; i++) {
      ans = add(ans, mul(cnt[i], sub(cnt[i], 1)));
    }
    cout << add(ans, 1) << endl;
    return 0;
  }
  long long now = 0, ans = 0;
  for (long long i = 0; i < k; i++) {
    ind[now] = i;
    now = (now + pr.back()) % k;
  }
  for (long long i = n - 1; i >= 0; i--) {
    inc(ind[pr[i + 1]], 1);
    long long now = mul(get(k - 1), m / k);
    long long r = ind[pr[i]], l = r - m % k + 1;
    if (l < 0) {
      now = add(now, sub(get(k - 1), get(k + l - 1)));
      now = add(now, get(r));
    } else {
      now = add(now, sub(get(r), get(l - 1)));
    }
    ans = add(ans, mul(now, m));
  }
  for (long long i = 0; i < N; i++) t[i] = 0;
  for (long long i = 1; i < n; i++) {
    inc(ind[pr[i]], 1);
    long long now = mul(get(k - 1), m / k);
    long long r = ind[(pr[i] - pr.back() + k) % k], l = r - m % k + 1;
    if (l < 0) {
      now = add(now, sub(get(k - 1), get(k + l - 1)));
      now = add(now, get(r));
    } else {
      now = add(now, sub(get(r), get(l - 1)));
    }
    ans = add(ans, mul(now, m));
  }
  if (pr.back() * m % k == 0) {
    ans = sub(ans, mul(n, m) - 1);
  }
  cout << ans << endl;
  return 0;
}

```