Canvas Color Happiness

Little G wishes to repay Little C for his apple by gifting him a canvas. The canvas is represented 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 sequence. If exactly \(K\) colors appear exactly \(S\) times, then his happiness increases by \(W_{K}\).

Your task is to compute the sum of happiness over all possible painting schemes modulo \(1004535809\). Formally, consider all sequences \(a_1,a_2,\dots,a_N\) where \(a_i\) is one of the \(M\) colors. Let \(f_i\) be the frequency of color \(i\) in the sequence. Define \(K = |\{ i : f_i = S\}|\). The total happiness contributed by this sequence is \(W_K\). You need to calculate

[ \sum_{\text{all sequences}} W_{#{ i : f_i = S }} \mod 1004535809 ]

Note: When \(S = 0\), a color is counted if it does not appear in the sequence.

inputFormat

The first line contains three integers \(N, M, S\) where \(N\) is the length of the canvas, \(M\) is the number of colors, and \(S\) is the specific frequency to check.

The second line contains \(M+1\) integers: \(W_0, W_1, \dots, W_M\) where \(W_k\) is the happiness when exactly \(k\) colors appear exactly \(S\) times.

outputFormat

Output one integer: the sum of the happiness of all painting schemes, taken modulo \(1004535809\).

sample

2 2 1
3 5 7

20