Bob is investigating properties of integer sequences in an attempt to solve George's least favourite problem: Maintaining A Sequence!

To help Bob achieve his dreams, George gives Bob a warm up problem:

How many ordered sequences of $N$ non-negative integers are such that each element is a member of the set $\{a_1,a_2,\dots ,a_K\}$ and whose sum is at most $M$?

Bob points out that this number might be a bit large, so George lets him return the answer modulo ${10}^9+7$.

Can you help Bob solve his warm up problem?

Constraints

For all subtasks:

$0\le a_k\le M$

Each $a_i$ is guaranteed to be pairwise distinct.

Subtask 1 [20%]

$1\le N,M,K\le 500$

Subtask 2 [20%]

$a_k=k-1$ for all $1\le k\le K$

$K=M$

$1\le N\le {10}^{18}$

$1\le M,K\le 2500$

Subtask 3 [20%]

$1\le N\le {10}^{18}$

$1\le M,K\le 500$

Subtask 4 [40%]

$1\le N\le {10}^{18}$

$1\le M,K\le 2500$

Input Specification

The first line of input will contain three space separated integers, $N$, $M$, and $K$.
The second line of input will contain $K$ space-separated integers, $a_1,a_2,\dots ,a_K$.

Output Specification

The number of sequences that satisfy the given conditions, modulo ${10}^9+7$.

Sample Input

2 3 4
1 3 2 0

Sample Output

10

Explanation for Sample

The possible sequences are: $[0,0]$, $[0,1]$, $[0,2]$, $[0,3]$, $[1,0]$, $[1,1]$, $[1,2]$, $[2,0]$, $[2,1]$, and $[3,0]$.