#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int n, m, k, a[200200], s[200200], id[200200];
ll c[200200], pl[400400], ans;
int main() {
  cin.tie(0)->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;
  int p = s[n];
  if (!p) {
    for (int i = 1; i <= n; i++) c[s[i]] += m;
  } else {
    vector<int> v;
    for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
    for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
    for (int i = 0; i < k; i++) id[v[i]] = i;
    for (int i = 1; i <= n; i++) {
      pl[0] += m / k, pl[k] -= m / k;
      int u = id[s[i] % k];
      pl[u]++, pl[u + m % k]--;
    }
    for (int i = 0; i < 2 * k; i++) {
      if (i) pl[i] += pl[i - 1];
      c[v[i]] += pl[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    c[s[i]]--;
    int x = (1ll * p * m % k + s[i]) % k;
    (ans += c[x]) %= mod;
    c[x]++;
  }
  (ans *= m) %= mod;
  if (1ll * p * m % k == 0) ans = (ans + 1) % mod;
  cout << ans;
}

### Prompt

Your challenge is to write 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;
using ll = long long;
const int mod = 1e9 + 7;
int n, m, k, a[200200], s[200200], id[200200];
ll c[200200], pl[400400], ans;
int main() {
  cin.tie(0)->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;
  int p = s[n];
  if (!p) {
    for (int i = 1; i <= n; i++) c[s[i]] += m;
  } else {
    vector<int> v;
    for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
    for (int i = 1, j = 0; i <= k; i++, j = (j + p) % k) v.push_back(j);
    for (int i = 0; i < k; i++) id[v[i]] = i;
    for (int i = 1; i <= n; i++) {
      pl[0] += m / k, pl[k] -= m / k;
      int u = id[s[i] % k];
      pl[u]++, pl[u + m % k]--;
    }
    for (int i = 0; i < 2 * k; i++) {
      if (i) pl[i] += pl[i - 1];
      c[v[i]] += pl[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    c[s[i]]--;
    int x = (1ll * p * m % k + s[i]) % k;
    (ans += c[x]) %= mod;
    c[x]++;
  }
  (ans *= m) %= mod;
  if (1ll * p * m % k == 0) ans = (ans + 1) % mod;
  cout << ans;
}

```