408767: GYM103306 B Benford's Law

It is well known that Alan is a great mathematics enthusiast and he enjoys learning about mathematics facts. Recently, he read about a fact related to the first digit of numbers: the Benford's law, also known as the first-digit law. This law states that, in many collections of numbers from the real life, the most frequent first-digit is $$$1$$$. Moreover, it also states that the small digits are more likely to be the first-digits than the greater digits.

Alan read that the law is satisfied in many collections of numbers, such as river lengths, mountain heights, country populations, prices, people ages, house numbers, etc. In all of these collections, the digit $$$1$$$ is the most likely to be the first digit. Fascinated with this fact, Alan decided to make his own experiment and see if Benford's law is satisfied.

Before beginning with the experiment, Alan put $$$N$$$ buckets in a line and prepared $$$K$$$ balls. The experiment consists of $$$K$$$ steps. During the $$$i$$$-th step, he selects a bucket randomly and inserts the $$$i$$$-th ball in that bucket. The selection of the bucket is independent across each step and all buckets have the same probability of being selected.

Once all steps are finished, Alan will count the number of balls in each bucket and write the results in a list $$$L$$$. Let $$$c_d$$$ be the number of elements in $$$L$$$ which has $$$d$$$ as the first-digit, Alan wants to check if $$$c_1$$$ is the greater across all $$$c_d$$$ to see if Benford's law is satisfied (spoiler: for large values of $$$N$$$, Benford's law is satisfied in this experiment).

But when there was $$$M$$$ steps left to finish the experiment, Alan got tired of selecting buckets and inserting balls. So, he decided to ask you for help to finish his experiment. Given the number of balls in each bucket so far, what is the expected value of $$$c_1, c_2, \dots, c_9$$$ after performing the remaining $$$M$$$ steps?

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^5$$$ and $$$0 \leq M \leq 10^5$$$), the number of buckets in the experiment and the number of remaining steps.

The second line contains $$$N$$$ characters $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^5$$$), where $$$a_i$$$ is the number of ball in the $$$i$$$-th bucket so far.

Print $$$9$$$ lines. In the $$$i$$$-th line, print the expected value of $$$c_i$$$. We can show that the expected value can be represented in the form $$$\frac{p}{q}$$$, where $$$q \neq 0$$$ and $$$gcd(p,q) = 1$$$. Print the expected value as $$$p*q^{-1}$$$ modulo $$$998244353$$$.

10 0
0 1 2 2 0 3 1 0 1 1

4
2
1
0
0
0
0
0
0

1 13
0

1
0
0
0
0
0
0
0
0

13 17
0 1 5 3 1 0 2 1 4 2 5 2 1

126914455
362778099
800719102
15040153
238529512
843998224
698108042
421844973
174968030