Down the Rabbit Hole#715
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. 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.
The walls of the well were covered with numbers, and Alice started forming -digit numbers from these digits, dividing each by her favorite number . Strangely enough, all these numbers divided evenly by .
– 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.
The first line of the input file contains the numbers , , and , where is the number of digits covering the walls of the well (K \leq 10). The second line lists distinct digits. The number does not exceed , and the number does not exceed . All numbers in the file are non-negative integers.
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 -digit numbers must have exactly digits, with the first digit not being .
Example 1