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].
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b) {
  if (a + b < MOD)
    return a + b;
  return a + b - MOD;
}

int sub(int a, int b) {
  if (a >= b)
    return a - b;
  return a + MOD - b;
}

int mul(int a, int b) {
  return a * 1ll * b % MOD;
}

const int MAXN = 200'200;

int nxt[MAXN];
vector<int> order;
int id[MAXN];

int fenw[MAXN];

void fenw_add(int i, int x) {
  for (; i < MAXN; i = (i | (i + 1)))
    fenw[i] = add(fenw[i], x);
}

int fenw_get(int i) {
  int ans = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    ans = add(ans, fenw[i]);
  return ans;
}

int main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  int n, m, k;
  cin >> n >> m >> k;
  vector<int> A(n);
  for (int i = 0; i < n; ++i)
    cin >> A[i];
  vector<int> pref(n + 1);
  for (int i = 0; i < n; ++i)
    pref[i + 1] = (pref[i] + A[i]) % k;
  int sum_all = pref[n];
  if (sum_all == 0) {
    vector<int> cnt(k);
    int ans = 0;
    for(int i = 1; i <= n; ++i)
      cnt[pref[i]] = add(cnt[pref[i]], m);
    for(int i = 0; i < k; ++i)
      ans = add(ans, mul(cnt[i], sub(cnt[i], 1)));
    ans = add(ans, 1);
    cout << ans << '\n';
    return 0;
  }
  for (int i = 0; i < k; ++i)
    nxt[i] = (i + sum_all) % k;
  int cur = 0;
  for (int i = 0; i < k; ++i) {
    order.emplace_back(cur);
    cur = nxt[cur];
  }
  for (int i = 0; i < k; ++i)
    id[order[i]] = i;
  int ans = 0;
  //l % n <= r % n
  for (int i = n - 1; i >= 0; --i) {
    fenw_add(id[pref[i + 1]], 1);
    int current = 0;
    int tmp = m;
    current = mul(fenw_get(k), tmp / k);
    tmp %= k;
    int r = id[pref[i]];
    int l = r - tmp + 1;
    if (l < 0) {
      current = add(current, sub(fenw_get(k), fenw_get(k + l - 1)));
      current = add(current, fenw_get(r));
    } else {
      current = add(current, sub(fenw_get(r), fenw_get(l - 1)));
    }
    ans = add(ans, mul(current, m));
  }
  //l % n > r % n
  fill(fenw, fenw + k, 0);
  for (int i = 1; i < n; ++i) {
    fenw_add(id[pref[i]], 1);
    int tmp = m;
    int current = mul(fenw_get(k), tmp / k);
    tmp %= k;
    int r = id[(pref[i] + k - sum_all) % k];
    int l = r - tmp + 1;
    if (l < 0) {
      current = add(current, sub(fenw_get(k), fenw_get(k + l - 1)));
      current = add(current, fenw_get(r));
    } else {
      current = add(current, sub(fenw_get(r), fenw_get(l - 1)));
    }
    ans = add(ans, mul(current, m));
  }
  if (sum_all * m % k == 0)
    ans = sub(ans, sub(mul(n, m), 1));
  cout << ans << '\n';
  return 0;
}
