A ticket kiosk gives change using k distinct coin denominations, with an unlimited supply of each. Count the number of distinct ways to make change for amount T using these coins, where two ways are considered the SAME if they use the same number of coins of each denomination (the order in which coins are handed over does not matter). Since the count can be large, print it modulo 1000000007.

Input format

Line 1: two integers T k. Line 2: k distinct space-separated positive integers, the coin denominations.

Output format

A single integer: the number of distinct multisets of coins summing to exactly T, modulo 1000000007. (If T = 0, the only way is to use no coins, so the answer is 1.)

Constraints

• 0 ≤ T ≤ 3000
• 1 ≤ k ≤ 8
• 1 ≤ each denomination ≤ 200

5 2
1 2

3

3 1
2

0