1121번 - 도형

문제

1부터 N까지 번호가 매겨져 있는 선분이 있다. 각 선분의 길이가 주어진다. 이때, 이 선분을 이용해서 만들 수 있는 서로 다른 K각형의 개수를 출력하는 프로그램을 작성하시오. K각형의 한 변은 주어진 선분 중의 하나여야 한다. 그리고 각 선분은 한 번만 사용할 수 있다.

다각형이 서로 다른 것은, 두 다각형 A와 B가 있을 때, A에 쓰였는데, B에 쓰이지 않은 선분이 있다면, 두 다각형을 서로 다르다고 한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 선분의 길이가 주어진다. 길이는 50,000보다 작거나 같은 자연수이다. 셋째 줄에는 K가 주어진다. K는 3보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

힌트