근손실

웨이트 트레이닝을 좋아하는 대학원생이 있다. 이 대학원생은 현재 3대 운동 중량 500의 괴력을 가지고 있다. 다만 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때 3일이 지나면 중량이 488로 줄어든다. 따라서 운동을 하지 않고 가만히 있으면 중량은 매일 줄어들기만 한다.

다행히도 이 대학원생에게는 N개의 서로 다른 운동 키트가 있다. 하루에 키트 하나씩을 사용하며, 매일 어떤 키트를 사용할지는 마음대로 정할 수 있다. 운동 키트마다 중량 증가량이 정해져 있고, 사용할 때마다 즉시 중량이 증가한다. 서로 다른 운동 키트의 중량 증가량이 같을 수도 있지만, 그런 경우에도 서로 다른 키트로 본다. 각 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간 동안 항상 중량이 500 이상으로 유지되도록 N일간의 운동 계획을 세우려 한다. 1일차부터 N일차까지 모든 기간에서 어느 시점이든 중량이 500보다 작아지면 안 된다.

예를 들어 N=3, K=4이고, 각 운동 키트의 중량 증가량이 다음과 같다고 하자.

1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해 보자. 이 경우 운동 1일차에 중량이 3만큼 증가하지만 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 뒤 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 적용한다고 해 보자. 그러면 1일차부터 운동을 모두 마친 날까지 모든 시점에서 중량이 항상 500 이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 키트 하나씩을 사용하는 모든 경우 중에서 운동 기간 동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간 동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.