Time Limit: 1000ms
Memory Limit: 65536kb
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.
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.
OutputFor 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.
5 2 1 2 4 3 1 1 1 6 1 5
3 15 0