No.2243 Coaching Schedule
Problem Statement
Noya thinks that to get stronger at competitive programming, he needs to overcome his $M$ weak areas, areas $1,2,\dots ,M$.
Noya has $N$ friends who are competitive programming experts. The specialty of the $i$-th friend is area $A_i$, so the $i$-th friend is going to teach him area $A_i$.
Starting today, Noya will hold an intensive training period lasting $1$ or more days, and on each day of the period he chooses $1$ or more of his weak areas and trains in them. For every $1$ area he chooses, he is taught that area by exactly $1$ friend. However, since all the friends are busy, he will ask each of them to serve as a teacher on exactly $1$ day during the period.
Find the number of possible combinations of schedules on which the $N$ friends teach Noya, modulo $998244353$.
Constraints
- All inputs are integers
- $1\le M, N\le 10^5$
- $1\le A_i\le M\ (1\le i\le N)$
Input
$M$ $N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Find the number of possible combinations of schedules on which the $N$ friends teach Noya, modulo $998244353$.
Sample
Sample 1
Input
2 3 1 2 1
Output
10
Suppose that friends $1,2,3$ teach him on days $d_1,d_2,d_3$ of the training period, respectively.
The possible $(d_1,d_2,d_3)$ are the following $10$.
$(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),(1,1,2),(1,2,2),(2,1,1),(2,2,1)$
Sample 2
Input
100 13 9 9 9 9 9 9 9 9 9 9 9 9 9
Output
237554682
There are $100$ weak areas, but the friends' specialties are all area $9$.
Find the answer modulo $998244353$.
Sample 3
Input
10 13 2 7 1 8 2 8 1 8 2 8 4 5 9
Output
612761073
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia