CF1575C Cyclic Sum

设一个长度为 $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$ 取模后的结果。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m, k \leq 2 \times 10^5$，$k = 1$ 或 $k$ 是质数）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 2 \times 10^5$）。

输出一个整数，表示在 $b$ 中有多少个不同的区间，其区间内元素之和能被 $k$ 整除，答案对 $10^9 + 7$ 取模。

在第一个样例中，所有满足条件的区间为 $[1,4]$、$[2,3]$、$[3,5]$ 和 $[4,2]$。 在第二个样例中，其中一个满足条件的区间为 $[1, 5]$。 由 ChatGPT 4.1 翻译