Bara Bada Bastu
Time: 1.0 s Memory: 1024 MB
-
The Chalmers SaunaIn the Chalmers Sauna there are $R$ rows of benches, where each row has $S$ seats. As any sauna-goer knows, the upper benches are hotter and not everyone can take the heat.
One day, $N$ people want to go in the sauna. The $i$th person has a maximum row $r_i$, which is an integer between $1$ and $R$. This means that this person can only sit at rows $1, 2, \dots , r_i$.
Your task is to count in how many ways the $N$ people can sit in the sauna. The different seats are distinct, so if one person just moves around on the same row it still counts as different ways. Since the number can be quite large, output it modulo $10^9+7$.
Input
The first line contains three integers $N, R, S$ ($1 \leq N \leq \min (R\cdot S, 10^5)$, $1 \leq R,S, \leq 10^9$).
The second line contains $N$ integers $r_i$ ($1 \leq r_i \leq R$).
Output
Print one integer, the number of ways to arrange the $N$ people in the sauna, modulo $10^9+7$.
Sample Input 1 Sample Output 1 1 1 10 1
10
Sample Input 2 Sample Output 2 8 4 6 4 2 2 3 4 4 3 4
683750379
Sample Input 3 Sample Output 3 2 2 1 1 1
0
Sample Input 4 Sample Output 4 5 2000000 1984127 504 10008 504 103011 2130
0
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - A Bara Bada Bastu
- B Cold Night