#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 2e6 + 100;
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
struct base {
  double a, b;
  base() {}
  base(double x) : a(x), b(0) {}
  base(double x, double y) : a(x), b(y) {}
  friend base operator+(const base& a, const base& b) {
    return base(a.a + b.a, a.b + b.b);
  }
  friend base operator-(const base& a, const base& b) {
    return base(a.a - b.a, a.b - b.b);
  }
  friend base operator*(const base& a, const base& b) {
    return base(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
  }
  friend base operator/(const base& a, double b) {
    return base(a.a / b, a.b / b);
  }
};
int a[N], pref[N], suff[N], blocks[N];
ll res[N];
base b[N];
void fft(base* a, int n, bool inv) {
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n / 2;
    for (; j >= bit; bit /= 2) {
      j -= bit;
    }
    j += bit;
    if (i < j) {
      swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len *= 2) {
    double ang = 2 * pi / len * (inv ? -1 : 1);
    base wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      base w(1);
      for (int j = 0; j < len / 2; ++j) {
        base u = a[i + j], v = a[i + j + len / 2] * w;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        w = w * wlen;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; ++i) {
      a[i] = a[i] / n;
    }
  }
}
void multiply(int* fa, int* fb, ll* fc, int k) {
  int n = 1;
  while (n < k) {
    n *= 2;
  }
  n *= 2;
  for (int i = 0; i < n; ++i) {
    if (i < k) {
      b[i].a = fa[i];
      b[i].b = fb[i];
    } else {
      b[i] = base(0);
    }
  }
  fft(b, n, false);
  for (int i = 0; i < n; ++i) {
    b[i] = b[i] * b[i];
  }
  fft(b, n, true);
  for (int i = 0; i < k; ++i) {
    fc[i] = (ll(b[i].b + 0.5) + ll(b[i + k].b + 0.5)) / 2;
  }
}
void solve() {
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    a[i] %= k;
  }
  int ans = 0;
  if (m >= 2) {
    int cur_suff = 0;
    for (int i = n - 1; i >= 0; --i) {
      cur_suff += a[i];
      if (cur_suff >= k) {
        cur_suff -= k;
      }
      ++suff[cur_suff];
    }
    int cur_blocks = 0;
    for (int i = 0; i <= m - 2; ++i) {
      ++blocks[cur_blocks];
      cur_blocks += cur_suff;
      if (cur_blocks >= k) {
        cur_blocks -= k;
      }
    }
    multiply(suff, blocks, res, k);
    int pref = 0;
    for (int r = 0; r < n; ++r) {
      pref += a[r];
      if (pref >= k) {
        pref -= k;
      }
      int x = (pref == 0 ? 0 : k - pref);
      ans = (ans + res[x]) % MOD;
    }
  }
  ++pref[0];
  int cur_pref = 0;
  for (int r = 0; r < n; ++r) {
    cur_pref += a[r];
    if (cur_pref >= k) {
      cur_pref -= k;
    }
    ans = (ans + pref[cur_pref]) % MOD;
    ++pref[cur_pref];
  }
  int blocks = (ll(cur_pref) * (m - 1)) % k;
  int full = (ll(cur_pref) * m) % k;
  int cur_suff = 0;
  for (int i = 0; i < k; ++i) {
    suff[i] = 0;
  }
  for (int i = n - 1; i >= 0; --i) {
    int val = cur_pref + blocks;
    if (val >= k) {
      val -= k;
    }
    val = (val == 0 ? 0 : k - val);
    ans = (ans + suff[val]) % MOD;
    cur_suff += a[i];
    if (cur_suff >= k) {
      cur_suff -= k;
    }
    ++suff[cur_suff];
    cur_pref -= a[i];
    if (cur_pref < 0) {
      cur_pref += k;
    }
  }
  if (full == 0 && m >= 2) {
    --ans;
    if (ans < 0) {
      ans += MOD;
    }
  }
  if (full == 0 && m == 1) {
    --ans;
    if (ans < 0) {
      ans += MOD;
    }
  }
  if (full == 0) {
    ans -= n - 1;
    if (ans < 0) {
      ans += MOD;
    }
  }
  ans = (ll(ans) * m) % MOD;
  if (full == 0) {
    ++ans;
    if (ans >= MOD) {
      ans -= MOD;
    }
  }
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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;
using ull = unsigned long long;
const int N = 2e6 + 100;
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
struct base {
  double a, b;
  base() {}
  base(double x) : a(x), b(0) {}
  base(double x, double y) : a(x), b(y) {}
  friend base operator+(const base& a, const base& b) {
    return base(a.a + b.a, a.b + b.b);
  }
  friend base operator-(const base& a, const base& b) {
    return base(a.a - b.a, a.b - b.b);
  }
  friend base operator*(const base& a, const base& b) {
    return base(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
  }
  friend base operator/(const base& a, double b) {
    return base(a.a / b, a.b / b);
  }
};
int a[N], pref[N], suff[N], blocks[N];
ll res[N];
base b[N];
void fft(base* a, int n, bool inv) {
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n / 2;
    for (; j >= bit; bit /= 2) {
      j -= bit;
    }
    j += bit;
    if (i < j) {
      swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len *= 2) {
    double ang = 2 * pi / len * (inv ? -1 : 1);
    base wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      base w(1);
      for (int j = 0; j < len / 2; ++j) {
        base u = a[i + j], v = a[i + j + len / 2] * w;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        w = w * wlen;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; ++i) {
      a[i] = a[i] / n;
    }
  }
}
void multiply(int* fa, int* fb, ll* fc, int k) {
  int n = 1;
  while (n < k) {
    n *= 2;
  }
  n *= 2;
  for (int i = 0; i < n; ++i) {
    if (i < k) {
      b[i].a = fa[i];
      b[i].b = fb[i];
    } else {
      b[i] = base(0);
    }
  }
  fft(b, n, false);
  for (int i = 0; i < n; ++i) {
    b[i] = b[i] * b[i];
  }
  fft(b, n, true);
  for (int i = 0; i < k; ++i) {
    fc[i] = (ll(b[i].b + 0.5) + ll(b[i + k].b + 0.5)) / 2;
  }
}
void solve() {
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    a[i] %= k;
  }
  int ans = 0;
  if (m >= 2) {
    int cur_suff = 0;
    for (int i = n - 1; i >= 0; --i) {
      cur_suff += a[i];
      if (cur_suff >= k) {
        cur_suff -= k;
      }
      ++suff[cur_suff];
    }
    int cur_blocks = 0;
    for (int i = 0; i <= m - 2; ++i) {
      ++blocks[cur_blocks];
      cur_blocks += cur_suff;
      if (cur_blocks >= k) {
        cur_blocks -= k;
      }
    }
    multiply(suff, blocks, res, k);
    int pref = 0;
    for (int r = 0; r < n; ++r) {
      pref += a[r];
      if (pref >= k) {
        pref -= k;
      }
      int x = (pref == 0 ? 0 : k - pref);
      ans = (ans + res[x]) % MOD;
    }
  }
  ++pref[0];
  int cur_pref = 0;
  for (int r = 0; r < n; ++r) {
    cur_pref += a[r];
    if (cur_pref >= k) {
      cur_pref -= k;
    }
    ans = (ans + pref[cur_pref]) % MOD;
    ++pref[cur_pref];
  }
  int blocks = (ll(cur_pref) * (m - 1)) % k;
  int full = (ll(cur_pref) * m) % k;
  int cur_suff = 0;
  for (int i = 0; i < k; ++i) {
    suff[i] = 0;
  }
  for (int i = n - 1; i >= 0; --i) {
    int val = cur_pref + blocks;
    if (val >= k) {
      val -= k;
    }
    val = (val == 0 ? 0 : k - val);
    ans = (ans + suff[val]) % MOD;
    cur_suff += a[i];
    if (cur_suff >= k) {
      cur_suff -= k;
    }
    ++suff[cur_suff];
    cur_pref -= a[i];
    if (cur_pref < 0) {
      cur_pref += k;
    }
  }
  if (full == 0 && m >= 2) {
    --ans;
    if (ans < 0) {
      ans += MOD;
    }
  }
  if (full == 0 && m == 1) {
    --ans;
    if (ans < 0) {
      ans += MOD;
    }
  }
  if (full == 0) {
    ans -= n - 1;
    if (ans < 0) {
      ans += MOD;
    }
  }
  ans = (ll(ans) * m) % MOD;
  if (full == 0) {
    ++ans;
    if (ans >= MOD) {
      ans -= MOD;
    }
  }
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}

```