split the number

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

WAVwind’s granddaughter is fond of certain integral number, and named them her lucky number, when she meets unknown integer, she always disintegrates it to several different lucky numbers.

That is,the sum of these different lucky numbers is this unknown integer。And no two lucky number have the same value。She found there are lots of methods of doing this, but she is undergoing some bad time lately, and couldn’t work out how many methods exactly, so please give her a hand.

Input

The input consists of several test cases, end of the file The first line contains 2 numbers M,N, M presents the number to be disintegrated, (1<=M<=10^3) N presents the amount of lucky number (1<=N<=10^3) The second line contains N numbers, which are the lucky numbers ai (0<=ai<10^3)

Output

For each test case, output a integer, denoting the number of methods of disintegrating. The answer may be very large,please output the answer MOD 2011424

Sample Input

10  10
1 2 3 4 5 6 7 8 9 10

Sample Output

10

Hint

Source

NJUSTACMCONTEST--WAVwind

提交代码