exchanging-letters-icpc-7

There are n+2 people sitting in a line, numbered from 0 to n+1. Some K distinct people with numbers ranging between 1 and n (inclusive) have letters given to them. The role of people with letters is to give their letters to one person sitting adjacent to them. At the end of this procedure, let X denote the sum of the numbers of all the people who have letters.  Find the number of possible ways that X can equal a given number, T, modulo 10^9 + 7. 

Note, if a person has two letters, count him/her twice.

Input:

The first line contains three integers, N, K, and T, in that order. 

Next line consists of K integers, the numbers of the people who have letters. 

Output:

Output the answer to the problem.

Constraints:

1 ≤ N ≤ 2000
1 ≤ K ≤ 2000
1 ≤ T ≤ 4000000
1 ≤ Number of everyone who has a letter ≤ N

SAMPLE INPUT
3 1 1
2

SAMPLE OUTPUT
1

Explanation

In order for this to work, person 2 must pass the letter to person 1.  So, there is exactly 1 way.

Source: hackerearth | Difficulty: MEDIUM


Solutions: