#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 5;
const int M = 1000000007;
int ans, n, m, k, r;
int a[N], b[N], p[N], s[N];
int cnt[19][N];
void add(int &x, int y) {
  x += y;
  if (x >= M) x -= M;
}
void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += M;
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) b[i] = (b[i - 1] + a[i - 1]) % k;
  for (int i = 0; i < n; ++i) cnt[0][b[i]]++;
  r = p[0] = b[n];
  for (int i = 1; i <= 17; ++i) {
    for (int j = 0; j < k; ++j) {
      add(cnt[i][j], cnt[i - 1][j]);
      add(cnt[i][(j + r) % k], cnt[i - 1][j]);
    }
    r = r * 2 % k;
    p[i] = r;
  }
  r = 0;
  for (int i = 17; i >= 0; --i)
    if ((m >> i) & 1) {
      for (int j = 0; j < k; ++j) add(s[(j + r) % k], cnt[i][j]);
      r = (r + p[i]) % k;
    }
  ans = 0;
  for (int i = 0; i < n; ++i) {
    sub(s[b[i]], 1);
    add(ans, s[b[i]]);
    add(s[(b[i] + r) % k], 1);
  }
  ans = 1ll * ans * m % M;
  if (!r) add(ans, 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;
const int N = int(2e5) + 5;
const int M = 1000000007;
int ans, n, m, k, r;
int a[N], b[N], p[N], s[N];
int cnt[19][N];
void add(int &x, int y) {
  x += y;
  if (x >= M) x -= M;
}
void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += M;
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) b[i] = (b[i - 1] + a[i - 1]) % k;
  for (int i = 0; i < n; ++i) cnt[0][b[i]]++;
  r = p[0] = b[n];
  for (int i = 1; i <= 17; ++i) {
    for (int j = 0; j < k; ++j) {
      add(cnt[i][j], cnt[i - 1][j]);
      add(cnt[i][(j + r) % k], cnt[i - 1][j]);
    }
    r = r * 2 % k;
    p[i] = r;
  }
  r = 0;
  for (int i = 17; i >= 0; --i)
    if ((m >> i) & 1) {
      for (int j = 0; j < k; ++j) add(s[(j + r) % k], cnt[i][j]);
      r = (r + p[i]) % k;
    }
  ans = 0;
  for (int i = 0; i < n; ++i) {
    sub(s[b[i]], 1);
    add(ans, s[b[i]]);
    add(s[(b[i] + r) % k], 1);
  }
  ans = 1ll * ans * m % M;
  if (!r) add(ans, 1);
  cout << ans << endl;
  return 0;
}

```