12980번 - 좋아하는 수열

BOJ 알고리즘 캠프에 참가하는 사람들은 수열을 좋아한다. 각 사람은 수열을 얼마나 좋아하는지 나타내는 함수를 가지고 있다.

캠프의 강사인 성관이가 제일 좋아하는 수열은 오름차순으로 정렬되어 있는 수열이다. 성관이는 수열 S를 보면, 머리속으로 i < j이면서 S[i] < S[j]인 (i, j) 쌍의 개수를 보는 즉시 계산해낸다. 이 값을 성관이가 수열을 좋아하는 "점수"라고 한다.

홍준이는 아침에 오자마자 1부터 N으로 이루어진 순열을 칠판에 적어놓았다. 성관이는 301호에 들어오자마자 칠판을 바라보았고, 그 즉시 적혀있는 순열의 점수를 계산해냈다. 점심을 먹으면서 홍준이가 적은 순열이 무엇인지 다시 한 번 생각해 보려고 했다. 하지만, "점수"는 기억이 나지만 순열은 전혀 기억이 나지 않았다.

점심을 먹는 내내 칠판에 적혀있는 순열이 무엇인지 궁금했던 성관이는 점심을 먹고 301호에 들어오자마자 칠판을 쳐다보았다. 칠판에는 순열이 적혀있었지만, 일부 수는 지워져 있었다. 성관이는 이제 홍준이가 적은 순열이 무엇이었는지를 아침에 계산한 "점수"를 이용해서 다시 만들어보려고 한다.

성관이가 아침에 계산한 "점수"와 현재 칠판에 적혀있는 순열이 주어졌을 때, 순열을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 칠판에 적혀있는 순열의 크기 N과 아침에 계산한 점수 S가 주어진다. (1 ≤ N ≤ 100, 0 ≤ S ≤ 1,000,000,000)

둘째 줄에는 칠판에 적혀있는 순열이 순서대로 주어진다. 지워져 있는 수는 0으로 주어진다.

칠판에 적혀있는 순열은 1보다 크거나 같고, N보다 작거나 같은 수가 한 번씩 등장하는 순열이고, 지워져있는 수는 5개 이하이다.

첫째 줄에 점수가 S가 되게 순열을 채울 수 있는 방법을 출력한다.

첫 번째 예제의 경우에 점수가 5가 되는 순열은 (4, 1, 5, 2, 3)과 (4, 3, 1, 2, 5) 이다.

두 번째 예제의 경우에는 가능한 정답이 (1, 3, 4, 2), (1, 4, 2, 3), (2, 1, 4, 3), (2, 3, 1, 4), (3, 1, 2, 4) 이다.