칼도리아의 기사들

칼도리아의 왕은 해마다 생일이면 왕국의 기사들을 큰 마상 시합에 초대하는 전통이 있다. 명문가마다 가장 뛰어난 기사를 보내 명성과 영광을 얻으려 한다. 대회가 끝나면 왕은 우승자만 고르지 않고, 전체 $n$명의 기사를 최하위부터 최상위까지 순위대로 매긴다.

가문 $i$에 속한 기사의 수를 $k_i$로 나타낸다. 각 기사는 최대 한 가문에만 소속된다. 어느 가문에도 속하지 않은 기사가 있을 수도 있다. 가문은 왕국에서의 영향력 순서로 주어지며, 첫 번째 가문이 가장 영향력이 크다. 가장 강력한 가문의 기사 $k_1$명이 대회의 마지막 $k_1$자리를 차지하면, 그 가문은 왕과 왕관에 맞서 반란을 일으킨다. 두 번째 가문은 그만큼 강하지 않다. 그 가문의 기사 $k_2$명이 모두 최하위를 차지해도 큰 도발이기는 하지만, 단독으로 반란을 일으킬 수는 없다. 그러나 상위 두 가문의 기사가 모두 합쳐서 마지막 $k_1 + k_2$자리를 차지하면, 두 가문은 손을 잡고 왕과 싸운다. 일반적으로 상위 $\ell$개 가문의 기사들이 마지막 $k_1 + k_2 + \dots + k_\ell$자리를 차지하면 그들은 뭉쳐 반란을 일으킨다.

반란은 어떤 일이 있어도 막아야 한다. 왕은 종종 깊이 생각하지 않고 그 자리에서 순위를 정하므로, 왕실 수석 수학자에게 반란으로 이어지지 않는 순위가 몇 가지인지 세라는 임무가 맡겨졌다.

첫 줄에 기사의 수 $n$ ($1 \leq n \leq 10^6$)과 가문의 수 $h$ ($0 \leq h \leq 5000$)가 주어진다. 이어서 $h$개의 줄이 주어지며, $i$번째 줄에는 가문 $i$의 기사 수 $k_i$ ($1 \leq k_i \leq n$)가 하나의 정수로 주어진다. 모든 가문에는 적어도 한 명의 기사가 있다. 또한 $\sum_{i=1}^h k_i \leq n$이 성립한다.

반란으로 이어지지 않는 순위의 개수를 출력한다. 이 수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.