barcode-monk-1

You have n-strip colorless bar code, where each strip is of unit length. You are given k brushes having their own different width. Using a brush of width w you can paint at a time exactly w consecutive strips on a bar code with black color, with the condition that initially all those w strips should be colorless. You can use any brush infinite times.

Find the number of distinct bar codes that you can create. Two bar codes are considered different if there exists at least one strip that is black in first and colorless in other. Print your answer modulo 10^9+7.

Input:

First line of input contains two space separated integers n and k denoting number of strips on bar code and number of brushes respectively. Next line contains k space separated integers, the i^th integer denoting the width of i^th brush.

Output:

Output in single line, your answer modulo 10^9+7.

Constraints:

1 ≤ n , k ≤ 10^3 
1 ≤ width of i^th brush (wi) ≤ 10^3

SAMPLE INPUT
3 1
1

SAMPLE OUTPUT
8

Explanation

Here are the possible bar codes that you can generate on strip of size 3 and brush of width 1. (0-white, 1-black)

000
001
010
100
011
101
110
111
Hence answer is 8.

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions: