C. Cyclic Sumtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputDenote 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.InputThe 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).OutputOutput 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.ExamplesInput
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
NoteIn 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].
5 1 5
1 2 3 4 3

4 
['data structures', 'fft', 'number theory', '*3000']