동전 조합 세기

동전의 종류가 주어졌을 때, 주어진 금액을 만들 수 있는 서로 다른 조합의 수를 구하시오.

각 동전은 원하는 만큼 사용할 수 있다. 동전의 순서만 다른 경우는 같은 방법으로 본다.

첫 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 세 줄로 이루어진다.

• 첫 줄에는 동전 종류의 수 N (1 <= N <= 20)이 주어진다.
• 둘째 줄에는 N가지 동전의 금액이 오름차순으로 주어진다. 각 금액은 1 이상 10000 이하의 정수이다.
• 셋째 줄에는 만들어야 하는 금액 M (1 <= M <= 10000)이 주어진다.

방법의 수는 $2^{31}-1$보다 작다고 가정해도 된다.

각 테스트 케이스마다, 주어진 동전으로 금액 M을 만드는 조합의 수를 한 줄에 하나씩 출력한다.