상금 배정

Nlogonia에서 역대 최고의 Nlogonia 프로그래머를 가리는 프로그래밍 대회가 열린다.

이 대회에는 N명의 참가자가 있고 동점은 없다. 즉, 모든 참가자는 1부터 N까지의 순위를 가지며 모든 순위는 서로 다르다. 순위가 낮을수록 더 좋은 성적이다.

대회 조직위원회는 각 참가자에게 최대 R 레이팅 포인트를 상금으로 주기로 했고, 더 좋은 성적을 낸 참가자에게 공정하기 위해 어떤 참가자도 자신보다 순위가 낮은 참가자보다 적은 레이팅 포인트를 받지 않는다.

하지만 일부 참가자는 더욱 욕심이 많아 더 많은 레이팅 포인트를 받아야 만족한다. 순위 i인 참가자는 상금으로 최소 pi 레이팅 포인트를 받아야 만족한다.

호기심 많은 조직위원 Ina는 조직위원회의 조건을 만족하면서 모든 참가자를 만족시키도록 상금을 나눠 주는 방법이 몇 가지인지 궁금해한다. 이 수는 매우 클 수 있으므로 109 + 7로 나눈 나머지를 계산해야 한다.

두 방법은 적어도 한 참가자가 받는 상금 액수가 다르면 서로 다른 방법이다.

첫째 줄에 두 정수 N과 R (1 ≤ N ≤ 5000, 1 ≤ R ≤ 109)이 주어진다. 각각 참가자의 수와 각 참가자가 상금으로 받을 수 있는 레이팅 포인트의 최댓값이다.

둘째 줄에 N개의 정수 pi (1 ≤ pi ≤ 109)가 주어진다. 순위 i인 참가자가 만족하기 위해 상금으로 받아야 하는 최소 레이팅 포인트이다.

상금을 나눠 주는 서로 다른 방법의 수를 109 + 7로 나눈 나머지를 출력한다.