408767: GYM103306 B Benford's Law
Description
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?
InputThe 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.
OutputPrint $$$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$$$.
ExamplesInput10 0 0 1 2 2 0 3 1 0 1 1Output
4 2 1 0 0 0 0 0 0Input
1 13 0Output
1 0 0 0 0 0 0 0 0Input
13 17 0 1 5 3 1 0 2 1 4 2 5 2 1Output
126914455 362778099 800719102 15040153 238529512 843998224 698108042 421844973 174968030