CF1575C.Cyclic Sum

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

将长度为 $n$ 的循环序列定义为数组 $s$，其中 $s_n$ 与 $s_1$ 相邻。当 $l < r$ 时，区间 $s[r, l]$ 表示 $s[r, n]$ 与 $s[1, l]$ 的拼接。

给定一个由 $n$ 个整数组成的数组 $a$。定义 $b$ 为将 $a$ 重复 $m$ 次后得到的循环序列。注意，$b$ 的长度为 $n \cdot m$。

给定一个整数 $k$，满足 $k = 1$ 或 $k$ 为质数。求 $b$ 中满足区间内元素之和能被 $k$ 整除的不同区间的个数。

若两个区间的下标集合不同，则认为它们是不同的区间。例如，当 $n = 3$ 且 $m = 2$ 时，区间 $s[2, 5]$ 的下标集合为 $\{2, 3, 4, 5\}$，而区间 $s[5, 2]$ 的下标集合为 $\{5, 6, 1, 2\}$。特别地，区间 $s[1, 6], s[2,1], \ldots, s[6, 5]$ 被视为同一个区间。

输出答案对 $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$).

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m, k \leq 2 \cdot 10^5$，且 $k = 1$ 或 $k$ 为质数）。

第二行包含 $n$ 个整数 $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$.

输出一个整数，表示数组 $b$ 中有多少个不同的子段，其元素之和能被 $k$ 整除，结果对 $10^9 + 7$ 取模。

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

在第一个例子中，所有有效的区间为 $[1,4]$、$[2, 3]$、$[3, 5]$ 和 $[4, 2]$。

在第二个例子中，一个有效的区间是 $[1, 5]$。