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 <bits/stdc++.h>
using namespace std;
long long f[25 - 1][200005];
long long cur[200005];
long long a[200005], b[200005], len[200005];
signed main() {
  long long n, m, k;
  cin >> n >> m >> k;
  for (long long i = 0; i < n; i++) scanf("%lld", &a[i]);
  b[0] = a[0];
  f[0][b[0]]++;
  for (long long i = 1; i < n; i++) {
    b[i] = (b[i - 1] + a[i]) % k;
    f[0][b[i] % k]++;
    f[0][b[i] % k] %= 1000000007;
  }
  long long tmp = b[n - 1];
  for (long long i = 0; i < 25; i++) {
    len[i] = tmp;
    tmp *= 2;
    tmp %= k;
  }
  for (long long i = 1; i < 25; i++) {
    for (long long j = 0; j < k; j++) {
      f[i][(j - len[i - 1] + k) % k] =
          (f[i - 1][(j - len[i - 1] + k) % k] + f[i - 1][j]) % 1000000007;
    }
  }
  tmp = 0;
  for (long long i = 25 - 1; i >= 0; i--) {
    if (!(m & (1ll << i))) continue;
    for (long long j = 0; j < k; j++) {
      cur[j] += f[i][(j - tmp + k) % k];
      cur[j] %= 1000000007;
    }
    tmp += len[i];
    tmp %= k;
  }
  long long ans = 0;
  if (tmp == 0) {
    cur[0]--;
    cur[0] += 1000000007;
    cur[0] %= 1000000007;
    ans += cur[0];
    ans %= 1000000007;
    cur[tmp]++;
    cur[tmp] %= 1000000007;
    for (long long i = 1; i < n; i++) {
      cur[b[i]]--;
      cur[b[i]] += 1000000007;
      cur[b[i]] %= 1000000007;
      ans += cur[b[i]];
      ans %= 1000000007;
      cur[(tmp + b[i]) % k]++;
      cur[(tmp + b[i]) % k] %= 1000000007;
    }
    ans = ans * m % 1000000007;
    ans++;
  } else {
    cur[0]--;
    cur[0] += 1000000007;
    cur[0] %= 1000000007;
    ans += cur[0];
    ans %= 1000000007;
    cur[tmp]++;
    cur[tmp] %= 1000000007;
    for (long long i = 1; i < n; i++) {
      cur[b[i]]--;
      cur[b[i]] += 1000000007;
      cur[b[i]] %= 1000000007;
      ans += cur[b[i]];
      ans %= 1000000007;
      cur[(tmp + b[i]) % k]++;
      cur[(tmp + b[i]) % k] %= 1000000007;
    }
    ans = ans * m % 1000000007;
  }
  cout << ans << endl;
}
