City Flooding

William is playing a city simulation game: the main objective is to save the mayor’s life in the event of natural disasters $\dots$ and the weather forecast just warned William about an imminent flooding!

The city can be seen as a straight line: there are $N$ positions numbered from $0$ to $N - 1$. The mayor’s house is in position $K$. During the flooding, $L$ liters of water will flow from the left corner to position $0$ first, then to position $1$ and so on. In order to stop the water from flooding the mayor’s home, you need to place $N - 1$ manholes in every position except the one in which the house of the mayor is located. Luckily, you have exactly $N - 1$ manholes left in the game inventory, however, they are all different. Some are able to “subtract” more water than others: no two manholes will subtract the same amount!

For example, let’s say that $L = 100$ liters of water will rain down during the flooding. Moreover, let’s assume that the city has $N = 5$ total positions (numbered from $0$ to $4$), and that $K = 3$ is the position of the mayor’s house. In this case, we would have $N - 1 = 4$ manholes in our inventory. Let’s say that the $4$ manholes are able to remove, respectively: $15$, $80$, $20$ and $50$ liters of water.

In this case, we can see that there are only $6$ ways to arrange the manholes so that some water will hit the mayor’s home (indicated with a $\star$). To be precise, $100$ - ($15 + 20 + 50$) = $15$ liters of water will reach his home.

So, the number of bad manhole arrangements is $6$. Since the total number of arrangements is $4! = 24$, we can deduce that the answer for this case is $24 - 6 = 18$.

Compute how many ways William can put the $N - 1$ manholes in such a way that will keep the mayor’s house dry during the flooding.

Input data

The first line contains a single integer: $L$. The second line contains two integers: $N$ and $K$. The third line contains $N - 1$ integers $V_0, V_1, \dots, V_{N-1}$: the “capacity” of the manholes.

Output data

You need to write a single line with an integer: the number of good manhole arrangements. Since this number can be huge, just print the remainder when dividing it by $10 \ 007$.

Constraints and clarifications

• $1 \leq L \leq 1 \ 000$.
• $2 \leq N \leq 100$.
• $0 \leq K \leq N - 1$.
• $0 \leq V_i \leq 1 \ 000$ for each $i = 0 \dots N - 2$.
• All $V_i$ values are different.

Example 1

stdin

100
5 3
15 80 20 50

stdout

18

Explanation

The first sample case is the one described in the task statement.

Example 2

stdin

100
10 5
34 30 16 9 18 14 27 10 15

stdout

5415

Explanation

In the second sample case there are $155 \ 520$ valid combinations. Since we are requested to print only the remainder of the division by $10 \ 007$, the answer is $155 \ 520$ % $10 \ 007$ = $5 \ 415$.