Gourmeten

문제

Den franska gourmeten Frank är en väl respekterad gourmet; hans yrke är att gå runt till olika restauranger, äta av deras mat och ge sitt omdöme om restaurangen. Men han bär på en hemlighet: han är egentligen bara intresserad av att äta så mycket som möjligt och i vilken ordning som helst!

Frank förstår dock att en äkta gourmet inte kan äta hur som helst, t.ex. börja med sin dessert och avsluta med en sallad. Därför ber han om din hjälp att ta fram en lista med alla olika sätt att ordna maträtterna under en bjudning, så han kan välja ut den ordning som är finast.

På bjudningen har Frank $MM$ minuter på sig att äta. Restaurangen bjuder på $NN$ olika rätter som han kan äta hur många portioner som helst av. Varje rätt $ii$ tar ett visst givet antal minuter $T_{i}T\_i$ att äta. Frank vill äta kontinuerligt under alla de $MM$ minuter han har på sig, och han vill hinna äta klart alla rätter han påbörjat. Han vill aldrig påbörja en ny rätt innan han ätit färdigt den förra. Din uppgift är att skriva ett program som räknar ut på hur många olika sätt han kan lägga upp middagen, givet dessa restriktioner.

입력

På första raden står ett heltal $MM$, antalet minuter, där $1\le M\le 1,0001\; \backslash le\; M\; \backslash le\; 1,000$.

På andra raden står ett heltal $NN$, antalet rätter, där $1\le N\le 301\; \backslash le\; N\; \backslash le\; 30$.

Därefter följer $NN$ rader med ett heltal $T_{i}T\_i$ på varje rad, tiden det tar att äta varje rätt, där $1\le T_i\le 2001\; \backslash le\; T\_i\; \backslash le\; 200$.

출력

Programmet ska skriva ut antalet möjliga sätt Frank kan äta under exakt $MM$ minuter. Svaret kommer alltid understiga $22$ miljarder.

힌트

Frank ska alltså äta under $1010$ minuter och han har $22$ rätter att välja på, t.ex. sallad (tar $33$ minuter att äta), och paj ($77$ minuter). Det finns bara två sätt att äta på: först paj sen sallad eller tvärtom. Äter han bara sallad kommer han antingen att bli klar för snabbt ($3\text{ portioner}=9\text{ minuter}3\; \backslash text\{\; portioner\}\; =\; 9\; \backslash text\{\; minuter\}$) eller för sent ($4\text{ portioner}=12\text{ minuter}4\; \backslash text\{\; portioner\}\; =\; 12\; \backslash text\{\; minuter\}$).

10
2
7
3

2

12
6
1
3
3
5
6
12

498