To repay Little C for his apples, Little G plans to give the art-loving Little C a canvas. This canvas can be abstracted as a sequence of length $N$, where each position can be painted with one of $M$ colors.

However, Little C only cares about the number of colors that appear exactly $S$ times in the $N$ positions of the sequence. If there are $K$ colors that appear exactly $S$ times, Little C will gain a pleasure value of $W_K$.

Little C wants to know the sum of the pleasure values he can obtain over all possible coloring schemes, modulo $1004535809$.

Input

The first line contains three integers $N, M, S$. The next line contains $M + 1$ integers, where the $i$-th number represents $W_{i-1}$.

Output

Output a single integer representing the answer.

Examples

Input 1

8 8 3
3999 8477 9694 8454 3308 8961 3018 2255 4910

Output 1

524070430

Input 2

See color/color2.in in the contestant directory.

Output 2

See color/color2.ans in the contestant directory.