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 \cdot 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], \ldots, s[6, 5]$ are considered as the same segment.

Output the answer modulo $10^9 + 7$.

The first line contains three integers $n$, $m$, and $k$ ($1 \leq n, m, k \leq 2 \cdot 10^5$, $k = 1$ or $k$ is a prime number).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2 \cdot 10^5$).

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$.