데어리 퀸에서 잔돈 거슬러 주기

베시(Bessie)는 동네 데어리 퀸 가게에서 손님에게 잔돈을 거슬러 주는 아르바이트를 시작했다. 손가락 대신 발굽이 있어서, 베시는 특별히 제작된 금전 등록기를 사용한다.

어느 날 83센트를 거슬러 주던 베시는 과연 몇 가지 방법으로 거슬러 줄 수 있을지 궁금해졌다. 25센트 세 개와 1센트 여덟 개, 10센트 일곱 개와 1센트 세 개, 또는 1센트 83개로도 가능하니 방법이 아주 많아 보인다.

목표 금액 $N$ ($1 \le N \le 300$) 센트와 값이 $C_i$ ($1 \le C_i \le 200$)인 동전 $C$ ($1 \le C \le 8$) 종류가 주어질 때, 정확히 $N$ 센트를 만드는 서로 다른 방법의 수를 구하라. 각 동전은 개수 제한 없이 사용할 수 있다. 두 방법은 적어도 한 종류의 동전을 서로 다른 개수만큼 사용할 때 서로 다르다고 본다. 동전을 고르는 순서는 구별하지 않는다.

예를 들어 미국 화폐에서 8센트는 5센트 동전 하나와 1센트 동전 세 개로 만들 수도 있고, 1센트 동전 여덟 개로 만들 수도 있다. 1센트 세 개와 5센트 하나는 5센트 하나와 1센트 세 개와 같으므로, 8센트를 만드는 방법은 정확히 두 가지다. 어떤 동전 체계는 잔돈을 만들기에 마땅치 않아 답이 0이 될 수도 있다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $C$.
• 2번째 줄부터 $C+1$번째 줄까지: $i+1$번째 줄에는 정수 $C_i$가 하나씩 주어진다.

동전 값은 큰 값부터 작은 값 순으로 내림차순 정렬되어 있으며, 모든 값은 서로 다르다.

• 주어진 동전으로 $N$ 센트를 만드는 방법의 수를 한 줄에 출력한다. 답은 부호 있는 32비트 정수 범위에 들어간다고 보장된다.

재귀 또는 동적 계획법을 풀이 기법으로 고려해 보라.

예시로, 50, 25, 10, 5, 1 값의 동전으로 83센트를 만드는 159가지 방법 중 15가지는 다음과 같다:

0 x 50  0 x 25  0 x 10  0 x 5  83 x 1
0 x 50  0 x 25  0 x 10  1 x 5  78 x 1
0 x 50  0 x 25  0 x 10  2 x 5  73 x 1
0 x 50  0 x 25  0 x 10  3 x 5  68 x 1
0 x 50  0 x 25  0 x 10  4 x 5  63 x 1
0 x 50  0 x 25  0 x 10  5 x 5  58 x 1
0 x 50  0 x 25  0 x 10  6 x 5  53 x 1
0 x 50  0 x 25  0 x 10  7 x 5  48 x 1
0 x 50  0 x 25  0 x 10  8 x 5  43 x 1
0 x 50  0 x 25  0 x 10  9 x 5  38 x 1
0 x 50  0 x 25  0 x 10  10 x 5  33 x 1
0 x 50  0 x 25  0 x 10  11 x 5  28 x 1
0 x 50  0 x 25  0 x 10  12 x 5  23 x 1
0 x 50  0 x 25  0 x 10  13 x 5  18 x 1
0 x 50  0 x 25  0 x 10  14 x 5  13 x 1