split the number

Time Limit: 1000 ms

Memory Limit: 65535 ms


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.


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)


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