출근하기 싫어 2

이 문제는 출근하기 싫어 1과 굵은 글씨로 적힌 부분과 제한 조건만 다릅니다.

누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다.

동우가 다니는 회사는 신기한 회사이다. 총 $N$명의 직원이 있는데, 이 중 최대 $2$명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만 $2$명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.

동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 $M$시간 동안 $N$명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.

직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 $M$시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, $N$명의 직원이 출근한 조합의 경우의 수를 구하시오.

이때, $M$시간에 대해 매시 30분을 기준으로 출근해 있는 직원들의 목록이 한 번이라도 다른 경우 서로 다른 조합으로 간주한다. 현재는 정각이라 가정한다.

첫 번째 줄에 직원의 수 $N$과 동우가 살펴본 최근 시간의 길이를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1\le N, M\le 5\\,000)$

두 번째 줄에 $N$명의 직원이 최근 $M$시간 동안 출근한 시간 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. $(0\le A\_i \le M)$

직원이 출근한 조합으로 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

단, $10^9+7$은 소수이다.