시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB73721315130.943%

문제

버킷 리스트는 사람이 평생 해 보고 싶은 경험이나 이뤄보고 싶은 성과를 의미하는 말로, 영어 속어인 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$

예제 입력 1

2 6
2 3

예제 출력 1

6

다음과 같은 $6$가지 경우가 가능하다.

  • 첫 번째 일을 $1, 2$번째 단위시간에 진행하고, 두 번째 일을 $3, 4, 5$번째 단위시간에 진행한다.
  • 첫 번째 일을 $1, 2$번째 단위시간에 진행하고, 두 번째 일을 $4, 5, 6$번째 단위시간에 진행한다.
  • 첫 번째 일을 $2, 3$번째 단위시간에 진행하고, 두 번째 일을 $4, 5, 6$번째 단위시간에 진행한다.
  • 첫 번째 일을 $4, 5$번째 단위시간에 진행하고, 두 번째 일을 $1, 2, 3$번째 단위시간에 진행한다.
  • 첫 번째 일을 $5, 6$번째 단위시간에 진행하고, 두 번째 일을 $1, 2, 3$번째 단위시간에 진행한다.
  • 첫 번째 일을 $5, 6$번째 단위시간에 진행하고, 두 번째 일을 $2, 3, 4$번째 단위시간에 진행한다.

출처

Contest > Good Bye, BOJ > Hello, BOJ 2022! C번