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.
Constraints
Special property: $\forall 1 \le i \le m, W_i = 0$
For $100\%$ of the data, $0 \le W_i < 1004535809$.
| Test Case | $N$ | $M$ | $S$ | Special Property |
|---|---|---|---|---|
| 1 | $\le 10$ | $\le 5$ | $\le 3$ | None |
| 2 | .h=5 $\le 100$ | .h=5 $\le 100$ | .h=5 $\le 7$ | .h=3 None |
| 3 | ||||
| 4 | ||||
| 5 | .h=2 Yes | |||
| 6 | ||||
| 7 | .h=2 $\le 10^5$ | $\le 1000$ | .h=2 $\le 50$ | None |
| 8 | $\le 10^5$ | Yes | ||
| 9 | .h=2 $\le 10^7$ | $\le 1000$ | .h=2 $\le 80$ | None |
| 10 | $\le 10^5$ | Yes | ||
| 11 | .h=4 $\le 10^6$ | .h=2 $\le 50000$ | .h=4 $\le 80$ | .h=10 None |
| 12 | ||||
| 13 | .h=2 $\le 10^5$ | |||
| 14 | ||||
| 15 | .h=6 $\le 10^7$ | .h=3 $\le 50000$ | .h=6 $\le 150$ | |
| 16 | ||||
| 17 | ||||
| 18 | .h=3 $\le 10^5$ | |||
| 19 | ||||
| 20 |