Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

fft

number theory

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Cyclic Sum

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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

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

Examples

Input

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

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 05:24:29 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|