Assigning Prizes
Time limit2sMemory limit1024 MB
Count non-increasing prize sequences of length N with values in [1,R] where the i-th value is at least p_i, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Combinatorics, Sorting, Prefix sum
- Solved
- No attempts yet
Problem
A programming competition will be held in Nlogonia to determine the best Nlogonian programmer of all time.
The competition has N contestants and there are no ties, so every contestant is ranked from 1 to N and all ranks are distinct. A lower rank means a better result.
The organizers decided that each contestant receives a prize of at most R rating points, and, to be fair to the contestants who did better, no contestant receives fewer rating points than any contestant with a worse rank.
Some contestants are greedier and want more rating points to be happy. A contestant with rank i needs a prize of at least pi rating points to be happy.
Ina, a very curious organizer, wonders how many ways the prizes can be distributed so that the organizers' conditions hold and every contestant is happy. Since this number can be very large, compute it modulo 109 + 7.
Two ways are different if at least one contestant receives a different prize amount.
Input
The first line contains two integers N and R (1 ≤ N ≤ 5000, 1 ≤ R ≤ 109), the number of contestants and the maximum rating points each contestant can receive as a prize.
The second line contains N integers pi (1 ≤ pi ≤ 109), the minimum rating points the contestant ranked i needs to receive as a prize to be happy.
Output
Print the number of different ways to distribute the prizes modulo 109 + 7.