将大小为 $$$n$$$ 的循环序列表示为数组 $$$s$$$,使得 $$$s_n$$$ 与 $$$s_1$$$ 相邻。段$$$s[r, l]$$$,其中$$$l < r$$$ 是$$$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 \cdot 10^5$$$、$$$k = 1$$$ 或 $$$k$$$ 是素数)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$)。
输出
输出一个整数,表示 $$$b$$$ 中不同段的数量,其中段中元素的总和可被 $$$k$$$ 整除,模 $$$10^9 + 7$$$。
示例
输入 #1
5 1 5 1 2 3 4 3
输出 #1
4
输入 #2
5 1 5 1 2 3 4 5
输出 #2
5
输入 #3
5 4 5 1 2 3 4 5
输出 #3
125
注意
在第一个示例中,所有有效段为 $$$[1,4]$$$、$$$[2, 3]$$$、$$$[3, 5]$$$ 和 $$$[4, 2]$$$。
在第二个示例中,有效段之一是 $$$[1, 5]$$$。