Down the Rabbit Hole
Alice was growing weary of sitting with her sister by the riverbank. She glanced at her sister's book a few times, but it was devoid of pictures or dialogue.
"What's the use of a book," Alice pondered, "without pictures or conversations?"
Adventures of Alice in Wonderland (translated by N.M. Demurova)
"What's the use of solving problems," Alice mused, "if they have neither pictures nor a plot?"
So, Alice impulsively followed the white rabbit with red eyes into the rabbit hole, not considering how she would return. Initially, the hole was like a tunnel, then it abruptly plunged downward. Before she knew it, Alice was falling, as if into a deep well. Whether the well was very deep or she was descending slowly, she had ample time to think and wonder about what lay ahead. She first attempted to see what awaited her below, but it was too dark to discern anything. Then she began to look around...
The walls of the well were covered with numbers, and Alice started forming N-digit numbers from these digits, dividing each by her favorite number P. Strangely enough, all these numbers divided evenly by P.
– I wonder how many such numbers there are? – Alice said aloud. – Will I fall through the entire earth before I count them all? That would be amusing! I climb out – and everyone is upside down! What are they called?.. Antipathies, I think...
Try to determine how many such numbers exist... Since this number can be very large, provide the answer modulo 1,000,000,007.
Input
The first line of the input file contains the numbers K, N, and P, where K is the number of digits covering the walls of the well (K ≤ 10). The second line lists K distinct digits. The number N does not exceed 1000, and the number P does not exceed 100. All numbers in the file are non-negative integers.
Output
Output a single number – the solution to the problem. When constructing the numbers, each given digit can be used as many times as needed. The N-digit numbers must have exactly N digits, with the first digit not being 0.