미니 버킷 리스트

버킷 리스트는 사람이 평생 해 보고 싶은 경험이나 이뤄 보고 싶은 성과를 뜻하는 말로, 영어 속어인 Kick the bucket에서 유래했다. 한국에서는 잭 니컬슨과 모건 프리먼이 출연한 「버킷 리스트: 죽기 전에 꼭 하고 싶은 것들」이라는 영화가 방영된 뒤로 유명해진 말이다. 한별이도 자신이 하고 싶은 계획을 담은 버킷 리스트를 만들어 보기로 했지만, 무엇을 하고 싶은지 막상 쓰려니까 잘 떠오르지 않았다. 하지만 천릿길도 한 걸음부터라는 말이 있지 않은가. 한별이는 공책에 ‘2022년에 꼭 하고 싶은 것들’이라는 제목을 쓰고 미니 버킷 리스트라는 별명을 붙여 줬다. 그리고 차례차례 자신이 하고 싶은 일을 적어 나갔다. 한별이는 2021년을 추억하고 2022년을 맞이하기 위한 티파티에 미니 버킷 리스트를 가져가서 자신의 결심을 친구들에게 보여 주기로 했다.

한별이는 2022년에 하고 싶은 일이 가득 적힌 미니 버킷 리스트를 한 손에 들고, 반대 손으로는 홍차를 마시며 친구들에게 자신의 계획을 설명했다. 우선, 한별이는 2022년을 $K$ 개의 단위시간으로 나눴다. 그리고 $N$ 가지의 일을 계획했는데, 하나의 일은 연속된 시간을 사용하며, 하나의 단위시간에는 최대 한 가지의 일만 진행하기로 했다. 또한 모든 일은 2022년 안에 진행하기로 했다. 이 계획에 맞춰 한별이는 미니 버킷 리스트에 일을 몇 번째 단위시간부터 시작하는지, 일을 하는 데는 몇 개의 단위시간이 걸리는지, 또 어떤 마음가짐으로 일을 하려고 하는지를 순서 상관 없이 적었다. 이제 한별이가 미니 버킷 리스트를 보며 친구에게 자신의 계획을 읽어 줄 일만 남아 있었다. 한별이는 미니 버킷 리스트를 보여 주려고 홍차를 급하게 마시다가 사레가 들려서 홍차를 미니 버킷 리스트에 쏟아 버렸다! 한별이는 서둘러 홍차를 닦아 내고 미니 버킷 리스트를 확인해 봤지만, 일을 몇 번째 단위시간부터 시작하는지에 대한 정보가 모두 홍차에 번져 확인할 수 없게 되었다.

한별이는 슬펐지만 미니 버킷 리스트를 복구하기로 했다. 우선 현재 남아 있는 정보로부터 만들 수 있는 미니 버킷 리스트의 정보가 몇 가지인지 알아내려고 한다. 2022년이 나뉜 단위시간의 개수 $K$, 한별이의 미니 버킷 리스트에 있는 일의 수 $N$과, 한별이가 $i$ 번째 일을 하는 데 걸리는 단위시간의 수 $S_i$가 주어졌을 때, 복구된 미니 버킷 리스트로 가능한 경우의 수를 구하여라. 여기서 복구된 두 미니 버킷 리스트가 서로 다른 종류라는 것은 어떤 일에 대해서 그 일을 시작하는 단위시간이 서로 다르다는 것이다.

첫 번째 줄에, 한별이의 미니 버킷 리스트에 적힌 일의 수 $N$과 2022년이 나뉜 단위시간의 개수 $K$가 주어진다.

두 번째 줄에, $S_1, S_2, \cdots, S_N$이 공백으로 구분되어 주어진다. 이는 한별이가 $i$ 번째 일을 하는 데에 $S_i$ 개의 단위시간을 연속으로 사용한다는 것을 의미한다.

첫 번째 줄에, 복구된 미니 버킷 리스트로 가능한 경우의 수를 $1\,000\,000\,007 ( = 10^9 + 7)$로 나눈 나머지를 출력한다.

• $1 \le N \le 500\,000$
• $K \le 10^9$
• $1 \le S_i$ $(1 \le i \le N)$
• $S_1 + S_2 + \cdots + S_N \le K$