구르메텐

프랑스 미식가 프랭크는 널리 존경받는 음식 평론가이다. 그의 일은 여러 식당을 돌아다니며 음식을 맛보고, 각 식당에 대한 평가를 내리는 것이다. 그런데 그에게는 비밀이 있다. 사실 그는 가능한 한 많이 먹는 데에만 관심이 있고, 순서는 아무래도 상관없다.

하지만 진정한 미식가는 아무렇게나 먹을 수 없다는 것을 프랭크도 안다. 예를 들어 디저트로 시작해서 샐러드로 끝내는 식은 안 된다. 그래서 그는 만찬에서 요리를 배열하는 모든 방법을 나열해 달라고 부탁했다. 그중에서 가장 격식 있는 순서를 고르기 위해서이다.

프랭크는 만찬에서 $M$분 동안 먹을 수 있다. 식당은 $N$가지 요리를 내놓으며, 각 요리는 몇 인분이든 원하는 만큼 먹을 수 있다. 요리 $i$를 먹는 데는 $T_i$분이 걸린다. 프랭크는 $M$분 내내 쉬지 않고 먹기를 원하며, 시작한 요리는 모두 다 먹고 끝내기를 원한다. 앞의 요리를 다 먹기 전에는 새 요리를 시작하지 않는다. 이 규칙 아래에서 프랭크가 저녁을 차리는 방법이 몇 가지인지 세는 프로그램을 작성하라.

첫 번째 줄에 분 단위의 시간 $M$이 주어진다. ($1 \le M \le 1,000$)

두 번째 줄에 요리의 수 $N$이 주어진다. ($1 \le N \le 30$)

이어지는 $N$개의 줄에는 각 요리를 먹는 데 걸리는 시간 $T_i$가 한 줄에 하나씩 주어진다. ($1 \le T_i \le 200$)

프랭크가 정확히 $M$분 동안 먹을 수 있는 방법의 수를 출력한다. 답은 항상 20억보다 작다.

프랭크가 10분 동안 먹고, 고를 수 있는 요리가 2가지인 경우를 보자. 샐러드는 3분, 파이는 7분이 걸린다. 방법은 두 가지뿐이다. 파이를 먼저 먹고 샐러드를 먹거나, 그 반대이다. 샐러드만 먹으면 3인분이면 $9$분이라 너무 일찍 끝나고, 4인분이면 $12$분이라 너무 늦게 끝난다.