408943: GYM103388 A Assigning Prizes

A programming competition will be held in Nlogonia to determine who is the best Nlogonian programmer of all time.

The competition will have $$$N$$$ contestants and there are no ties, in other words, every contestant will be ranked in a position from $$$1$$$ to $$$N$$$ and all ranks are distinct. Lower ranks represent better results.

The event organizers decided that each contestant will receive a prize of at most $$$R$$$ rating points, and, to be fair to the competitors that performed better, a contestant will never receive fewer rating points than any other contestant with a worse ranking.

Some competitors, though, are more greedy and want to receive more rating points to be happy. A contestant with rank $$$i$$$ needs to receive a prize of at least $$$p_i$$$ rating points to be happy.

Ina, a very curious organizer, is wondering in how many ways it is possible to distribute the prizes to the contestants in order to satisfy the organization's conditions and make all contestants happy. Also, since this number can be very large, you should calculate it modulo $$$10^9+7$$$.

Two ways are different if at least one contestant receives a different prize amount.

The first line contains two integers $$$N$$$ and $$$R$$$ ($$$1 \leq N \leq 5000$$$, $$$1 \leq R \leq 10^9$$$), representing the number of contestants and the maximum amount of rating points that each contestant can receive as a prize, respectively.

The second line contains $$$N$$$ integers, $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), representing the minimum rating points the contestant ranked $$$i$$$ needs to receive as a prize to be happy.

Print the number of different ways to distribute the prizes modulo $$$10^9+7$$$.

2 5
4 1

9

3 10
7 1 10

1