시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 241 | 144 | 89 | 54.601% |
You just finished participating in a programming contest with your friend. Unfortunately, you were unable to All Kill the contest (i.e., solve all of the problems), but you are now wondering if there might be some strategy that would have solved all of the problems.
Solving a problem has two phases, a thinking phase and a coding phase. Your friend is responsible for all the thinking while you are responsible for all the coding.
For each problem, you’ve computed exactly how long it would take for you to code. However, before you can code a problem in contest, your friend needs to get the idea to solve it first. You aren’t sure how to estimate the time when your friend gets a solution idea, so you model it like this: For every problem, your friend gets the idea of how to solve this problem at a uniformly random minute during the contest. Each of these is an independent random variable. You can only code one problem at a time, so there may be several problems queued up at any moment of time. You always prioritize coding the lowest numbered problems first. You do this minute-by-minute, so you will switch to coding a lower-numbered problem if your friend gets the idea for it before you’re finished coding a higher-numbered problem, but you would prefer not to do this. Context switching is an expensive operation, even in the human brain!
The contest strategy can be modeled as follows for each minute:
You would like to know the probability of these two events happening together:
Let p be this probability, n be the number of problems in the contest and t be the number of minutes in the contest. It can be shown that p · tn is an integer. Output the value of (p · tn) (mod 998,244,353). Note that 998,244,353 is a large prime.
The first line of input contains two space-separated integers n (1 ≤ n ≤ 105) and t (1 ≤ t ≤ 108), where there were n problems in the contest, and the contest lasted t minutes.
Each of the next n lines contains a single integer x (1 ≤ x ≤ 103). These are the times to code each problem in minutes, in order. It is guaranteed that the sum of these times is less than or equal to t.
Output a single integer, which is (p · tn) (mod 998,244,353), where p is the probability of the two events mentioned above happening together.
3 5 1 2 1
60
5 5 1 1 1 1 1
1296