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 2\,500~

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 2\,500~

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]~.