[Login|Register]
Problems

Status

Rank

Problem 1116
Arcade Game
Time Limit: 1000ms
Memory Limit: 65536kb
Description

Toy is a rebellious boy who is addicted in electronic games and likes to throw himself into video arcades all day and all night. There are various kinds of game machines in the video arcade, having different games. Each game machine demands several token coins to be inserted in before a round, or the game would come to an end. The number of token coins needed by two different machines may be distinct.

Now, Toy, who has just spent up all the money stolen from his parents in exchange for N token coins decides to play a couple of rounds on a machine and then turn to another one, then play several rounds and change again...

Toy could play arbitrary number of rounds on any game machine, and not all the machines must be played on. Not until all the coins are exactly used up will Toy leave.

There are M different game machines labeled 1, 2, ..., M, respectively. The i-th machine demands Pi token coins each round, can you tell me how many ways could Toy play on these game machines? Note that only when the number of rounds played on a certain machine is unequal can you regard there are two ways.

Input

The input consists of multiple test cases.

Each test case is written in two lines. There are two integers N (1 <= N <= 1000) and M (1 <= M <= 1000) in the first line, followed by M integers P1, P2, ..., PM (1 <= Pi <= N <= 1000, i=1, 2, ..., M), separated by spaces in the second line.

Output
For each test case, output the number of ways in a single line. Since the answer may be quite large, you have to module it by 10007.
Sample Input
5 2
1 2
4 3
1 1 1
6 1
5
Sample Output
3
15
0
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.7ms with 1 query(s).