25962번 - 선우의 셋리스트

선우는 아주대학교의 $3$년 만의 대동제를 맞아 공연으로 노래를 열창해 아주대학교의 여심을 홀리고 싶다. 선우는 총 $N$($1\leq N \leq 10^{18}$)분의 공연을 기획하고 있는데, 어떤 노래를 어느 순서로 몇 번이나 부를지 정하지 못하고 있다.

예를 들어, 다음과 같은 후보곡들이 있다고 하자.

1. <아주바캉스>, 아주 강 같은 평화 - $3$분
2. <졸업할 수 있을까>, 컴공소년 - $2$분
3. <벌써 사년>, 브라운 관즈 - $1$분
4. <응급실>, 낫 이지 - $5$분
5. <이미 아픈 성적>, 요다 - $4$분

선우가 이 노래들로 $10$분의 공연을 구성한다면 [3번, 1번, 3번, 4번]와 같은 식으로 공연을 구성할 수 있다. 여기서 알 수 있듯이, 선우는 중간에 절대 쉬지 않는다! 또한 같은 노래를 여러 번 부를 수도, 어떤 후보곡은 쓰이지 않을 수도 있다. 이렇게 공연을 하는 데에 부르는 노래의 순서를 셋리스트라고 한다.

선우가 부를 수 있는 후보곡의 수와, 각 노래의 재생 시간이 주어질 때, 선우를 도와 정확히 $N$분의 공연을 할 수 있는 셋리스트의 경우의 수를 알려주자.

첫 번째 줄에 선우가 공연을 기획한 시간 $N$($1 ≤ N ≤ 10^{18}$)과 선우가 부를 수 있는 후보곡의 수 $M$($2 \leq M \leq 100\,000$)이 공백으로 구분되어 주어진다.

두 번째 줄부터 ($M+1$)번째 줄까지 각 줄에는 노래의 재생시간 $t_i$($1 \leq i \leq M$, $ 1 \leq t_{i} \leq 5$)가 주어진다.

첫 번째 줄에 선우가 공연을 위해 준비해야 하는 가능한 셋리스트의 경우의 수를 $1\,000\,000\,007$($=10^{9}+7$)로 나눈 나머지를 출력하시오.

셋리스트를 구성할 수 없다면 정답은 $0$이다.