| UTPC Contest 1-29-25 Div. 2 (Beginner) |
|---|
| Закончено |
It's Lunar New Year, and $$$n$$$ ($$$1 \leq n \leq 100$$$) lion dancers are performing a traditional lion dance through a grid-like corridor. The corridor is divided into $$$m$$$ ($$$1 \leq m \leq 10^5$$$) sections, arranged as columns of platforms. Each section $$$i$$$ consists of $$$k_i$$$ platforms ($$$n \leq k_i \leq 10^5$$$) stacked vertically in a grid-like structure. Each platform can hold exactly one dancer, and no two dancers can share the same platform at any time.
The dancers start their performance in the first column and must move through the grid from left to right. At each step, all $$$n$$$ dancers move as a team to the next column, each landing on one of the available platforms in the new section. This process continues until they reach the final column.
Additionally, the lion dancers are numbered from $$$1$$$ to $$$n$$$, with dancer $$$1$$$ always performing on the lowest platform and dancer $$$n$$$ on the highest platform in any column. This order must be maintained throughout the performance: if dancer A is below dancer B in one column, then dancer A must be below dancer B in every other column.
Your task is to determine the number of distinct ways the lion dancers can perform their routine, moving from the first column to the last. Two routines are considered distinct if, at any step, at least one dancer occupies a different platform compared to the other routine. Please output the answer mod $$$10^9+7$$$.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — the number of lion dancers and corridor sections respectively.
The second line contains $$$m$$$ integers, $$$k_1, k_2, … k_{m}$$$ ($$$n \leq k_i \leq 10^5$$$) — denoting the number of platforms in each column.
Output a single integer — the number of distinct ways the lion dancers can complete their performance mod $$$10^9+7$$$
2 32 3 2
3
1 53 2 1 4 2
48
10 819 12 10 11 16 19 12 13
823844000
| Название |
|---|


